[LeetCode] Construct Binary Tree from Preorder and Inorder Traversal

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

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

方法一：最先想到的就是递归，注意low、high的计算，还有初始时NULL情况的处理。。

从inorder中寻找pre的第一个，然后左右递归

 1 class Solution
 2 {
 3     public:
 4         TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder)
 5         {
 6             if(preorder.size() == 0 || inorder.size() == 0)
 7                 return NULL;
 8             return buildTree(preorder, 0, preorder.size()-1,
 9                               inorder, 0, inorder.size()-1);
10         }     
11               
12         TreeNode *buildTree(vector<int> &preorder, int low1, int high1,
13                             vector<int> &inorder, int low2, int high2)
14         {     
15             //cout << "==============" <<endl;
16             //cout << "low1 = 	" << low1 <<endl;
17             //cout << "high1= 	" << high1 <<endl;
18             //cout << "low2 = 	" << low2 <<endl;
19             //cout << "high2= 	" << high2 <<endl;
20               
21             TreeNode * p = new TreeNode(preorder[low1]);
22             if(low1 == high1)
23             {   
24                 return p;
25             }   
26             int index = 0;
27             for(index = low2; index < high2; index++)
28             {   
29                 if(inorder[index] == preorder[low1])
30                     break;
31             }
32             //cout << "index= 	" << index<<endl;
33 
34             if(index != low2)
35                 p->left = buildTree(preorder, low1+1,(low1+1) + (index-1-low2), inorder, low2, index-1);
36             if(index != high2)
37                 p->right = buildTree(preorder, high1 - (high2-index-1) ,high1, inorder, index+1, high2);
38 
39             return p;
40         }
41 } ;

方法二：迭代