LeetCode OJ：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.
从前序以及中序的结果中构造二叉树，这里保证了不会有两个相同的数字，用递归构造就比较方便了：

 1 class Solution {
 2 public:
 3     TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
 4         if(!preorder.size()) return NULL;
 5         return createTree(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);//边界条件应该想清楚
 6     }
 7 
 8     TreeNode* createTree(vector<int>& preOrder, int preBegin, int preEnd, vector<int>& inOrder, int inBegin, int inEnd)
 9     {
10         if(preBegin > preEnd) return NULL;
11         int rootVal = preOrder[preBegin];
12         int mid;
13         for(int i = inBegin; i <= inEnd; ++i)
14             if(inOrder[i] == rootVal){
15                 mid = i;
16                 break;
17             }
18         int len = mid - inBegin;    //左边区间的长度为mid - inBegin;
19         TreeNode * left = createTree(preOrder, preBegin + 1, preBegin + len, inOrder, inBegin, mid - 1);
20         TreeNode * right = createTree(preOrder, preBegin + len + 1, preEnd, inOrder, mid + 1, inEnd);
21         TreeNode * root = new TreeNode(rootVal);
22         root->left = left;
23         root->right = right;
24         return root;
25     }
26 };

java版本的代码如下所示，方法上与上面的没什么区别：

 1 public class Solution {
 2     public TreeNode buildTree(int[] preorder, int[] inorder) {
 3         return createTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
 4     }
 5     
 6     public TreeNode createTree(int[] preorder, int preBegin, int preEnd, int[] inorder, int inBegin, int inEnd){
 7         if(preBegin > preEnd)
 8             return null;
 9         int rootVal = preorder[preBegin];
10         int i = inBegin;
11         for(; i <= inEnd; ++i){
12             if(inorder[i] == rootVal)
13                 break;
14         }
15         int leftLen = i - inBegin;
16         TreeNode root = new TreeNode(rootVal);
17         root.left = createTree(preorder, preBegin + 1, preBegin + leftLen ,inorder, inBegin, i - 1); //这里的边界条件应该注意
18         root.right = createTree(preorder, preBegin + 1 + leftLen, preEnd, inorder, i + 1, inEnd);
19         return root;
20     }
21 }