EEPW论坛

Given preorder and inorder traversal of a tree, construct the binary tree.

Note: 

You may assume that duplicates do not exist in the tree.

前序和中序重构二叉树；

这里用dfs的思想：

1. class Solution {  

2. public:  

3.     TreeNode *dfs(vector<int> &preorder,int preStart,int preEnd,vector<int> &inorder,int inStart,int inEnd)  

4.     {  

5.         if(preStart > preEnd)  

6.             return NULL;  

7.         TreeNode *root = new TreeNode(preorder[preStart]);  

8.         int middle;  

9.         for(middle=inStart;middle<=inEnd;middle++)  

10.             if(inorder[middle] == root->val)  

11.                 break;  

12.         int leftLen = middle-inStart;  

13.         root->left = dfs(preorder,preStart+1,preStart+leftLen,inorder,inStart,middle-1);  

14.         root->right = dfs(preorder,preStart+leftLen+1,preEnd,inorder,middle+1,inEnd);  

15.         return root;  

16.     }  

17.       

18.     TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder)  

19.     {  

20.         int pre = preorder.size(),in = inorder.size();  

21.         if(pre==0 || in==0 || pre != in)  

22.             return NULL;  

23.         return dfs(preorder,0,pre-1,inorder,0,in-1);  

24.     }  

25. }; 

Given preorder and inorder traversal of a tree, construct the binary tree.

Note: 

You may assume that duplicates do not exist in the tree.

前序和中序重构二叉树；

这里用dfs的思想：

1. class Solution {  

2. public:  

3.     TreeNode *dfs(vector<int> &preorder,int preStart,int preEnd,vector<int> &inorder,int inStart,int inEnd)  

4.     {  

5.         if(preStart > preEnd)  

6.             return NULL;  

7.         TreeNode *root = new TreeNode(preorder[preStart]);  

8.         int middle;  

9.         for(middle=inStart;middle<=inEnd;middle++)  

10.             if(inorder[middle] == root->val)  

11.                 break;  

12.         int leftLen = middle-inStart;  

13.         root->left = dfs(preorder,preStart+1,preStart+leftLen,inorder,inStart,middle-1);  

14.         root->right = dfs(preorder,preStart+leftLen+1,preEnd,inorder,middle+1,inEnd);  

15.         return root;  

16.     }  

17.       

18.     TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder)  

19.     {  

20.         int pre = preorder.size(),in = inorder.size();  

21.         if(pre==0 || in==0 || pre != in)  

22.             return NULL;  

23.         return dfs(preorder,0,pre-1,inorder,0,in-1);  

24.     }  

25. };