[leetcode]Construct Binary Tree from Preorder and Inorder Traversal

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 public class Solution {
 2     public TreeNode buildTree(int[] preorder, int[] inorder) {
 3         if(preorder == null || inorder == null || preorder.length != inorder.length || preorder.length == 0) return null;
 4         int val = preorder[0],length = inorder.length;
 5         int mid = 0;
 6         for(int i = 0; i < length; i++){
 7             if(inorder[i] == val){
 8                 mid = i;
 9                 break;
10             }
11         }
12         int[] leftPre = Arrays.copyOfRange(preorder, 1, mid + 1);
13         int[] leftIn = Arrays.copyOfRange(inorder, 0, mid);
14         int[] rightPre = Arrays.copyOfRange(preorder, mid + 1, length);
15         int[] rightIn = Arrays.copyOfRange(inorder, mid + 1, length);
16         TreeNode root = new TreeNode(val);
17         root.left = buildTree(leftPre, leftIn);
18         root.right = buildTree(rightPre,rightIn);
19         return root;
20     }
21 }