### 题目

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

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

### 顺序遍历preorder$O(n\log_{}{n})$

  8
/ \
2  10


inorder118的后面，11就应该插在8的右节点，如果8的右节点不为空，则和右节点的10比较，11inorder中比10还要靠后，因此，插入作为10的右节点。

      8
/ \
2  10
\
11


#### 代码

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder.length == 0 || inorder.length == 0 || preorder.length != inorder.length) { return null; }
Map<Integer,Integer> inorderMap = new HashMap<>();
for (int i = 0; i < inorder.length; i++) { inorderMap.put(inorder[i],i); }
TreeNode root = new TreeNode(preorder[0]);
for (int i = 1; i < preorder.length; i++) {
int index = inorderMap.get(preorder[i]);
TreeNode cur = root;
while (cur != null) {
if (inorderMap.get(cur.val) < index) { // 新节点应当在这个节点的右子树
if (cur.right == null) {
cur.right = new TreeNode(preorder[i]); break;
} else {
cur = cur.right;
}
} else { // 新节点应当在这个节点的左子树
if (cur.left == null) {
cur.left = new TreeNode(preorder[i]); break;
} else {
cur = cur.left;
}
}
}
}
return root;
}
}


### 分治递归

• preorder = [14, 6, 4, 1, 3, 5, 12, 8, 7, 10, 13, 16, 15, 19, 17, 18, 20]
• inorder = [1, 3, 4, 5, 6, 7, 8, 10, 12, 13, 14, 15, 16, 17, 18, 19, 20]

#### 代码

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder.length == 0 || inorder.length == 0) { return null; }
return buildTreeRecur(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
}
public TreeNode buildTreeRecur(int[] preorder, int preLo, int preHi, int[] inorder, int inLo, int inHi) {
if (preLo > preHi) { return null; }
TreeNode root = new TreeNode(preorder[preLo]);
int indexInInorder = indexOf(inorder,inLo,inHi,preorder[preLo]);
int leftSize = indexInInorder - inLo;
int rightSize = inHi - indexInInorder;
root.left = buildTreeRecur(preorder,preLo+1,preLo+leftSize,inorder,inLo,indexInInorder-1);
root.right = buildTreeRecur(preorder,preLo+leftSize+1,preHi,inorder,indexInInorder+1,inHi);
return root;
}
// return the index of target number in the array
// [lo,hi], both sides are inclusive
public int indexOf(int[] nums, int lo, int hi, int target) {
for (int i = lo; i <= hi; i++) {
if (nums[i] == target) { return i; }
}
return -1;
}
}


### 去掉indexOf()函数

#### 代码

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder.length == 0 || inorder.length == 0) { return null; }
Map<Integer,Integer> inorderMap = new HashMap<>();
for (int i = 0; i < inorder.length; i++) {
inorderMap.put(inorder[i],i);
}
return buildTreeRecur(preorder,0,preorder.length-1,inorder,0,inorder.length-1,inorderMap);
}
public TreeNode buildTreeRecur(int[] preorder, int preLo, int preHi, int[] inorder, int inLo, int inHi, Map<Integer,Integer> inorderMap) {
if (preLo > preHi) { return null; }
TreeNode root = new TreeNode(preorder[preLo]);
int indexInInorder = inorderMap.get(preorder[preLo]);
int leftSize = indexInInorder - inLo;
int rightSize = inHi - indexInInorder;
root.left = buildTreeRecur(preorder,preLo+1,preLo+leftSize,inorder,inLo,indexInInorder-1,inorderMap);
root.right = buildTreeRecur(preorder,preLo+leftSize+1,preHi,inorder,indexInInorder+1,inHi,inorderMap);
return root;
}
}


#### 清理代码

public class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder.length == 0 || inorder.length == 0) { return null; }
Map<Integer,Integer> inorderMap = new HashMap<>();
for (int i = 0; i < inorder.length; i++) { inorderMap.put(inorder[i],i); }
return buildTreeRecur(preorder,0,0,inorder.length-1,inorderMap);
}
public TreeNode buildTreeRecur(int[] preorder, int cur, int lo, int hi, Map<Integer,Integer> inorderMap) {
if (lo > hi) { return null; }
TreeNode root = new TreeNode(preorder[cur]);
int indexInInorder = inorderMap.get(preorder[cur]);
int leftSize = indexInInorder - lo;
int rightSize = hi - indexInInorder;
root.left = buildTreeRecur(preorder,cur+1,lo,indexInInorder-1,inorderMap);
root.right = buildTreeRecur(preorder,cur+leftSize+1,indexInInorder+1,hi,inorderMap);
return root;
}
}