题目：
题解：
1、分治法（解法一）
解题思路：
复杂度分析：
时间复杂度 O(N) ： 其中 NN 为树的节点数量。初始化 HashMap 需遍历 inorder ，占用 O(N) 。递归共建立 N 个节点，每层递归中的节点建立、搜索操作占用 O(1) ，因此使用 O(N) 时间。
空间复杂度 O(N) ： HashMap 使用 O(N) 额外空间；最差情况下（输入二叉树为链表时），递归深度达到 N ，占用 O(N) 的栈帧空间；因此总共使用 O(N) 空间。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28class Solution {
HashMap<Integer, Integer> map;
public TreeNode buildTree(int[] preorder, int[] inorder) {
map = new HashMap<>();
// 将中序遍历的数组放入map集合，key为它的值，value为它的索引，以便之后找到中序遍历的根节点的位置
for (int i = 0; i < inorder.length; i++) {
map.put(inorder[i],i);
}
return buildTree(preorder,0,preorder.length -1,inorder,0,inorder.length -1);
}
private TreeNode buildTree(int[] preorder, int preLeft, int preRight, int[] inorder, int inLeft, int inRight) {
if (preLeft > preRight || inLeft > inRight) {
return null;
}
int rootValue = preorder[preLeft];
// 将根节点赋值给root
TreeNode root = new TreeNode(rootValue);
// 拿到根节点在中序遍历中的位置
int pIndex = map.get(rootValue);
// 递归找它的左右子树节点
root.left = buildTree(preorder,preLeft + 1,preLeft + pIndex - inLeft, inorder ,inLeft,pIndex -1);
root.right = buildTree(preorder,preLeft + pIndex - inLeft + 1,preRight, inorder ,pIndex + 1,inRight);
return root;
}
}
1、分治法（解法二）
解题思路：
复杂度分析：
- 时间复杂度 O(N) ： 其中 NN 为树的节点数量。初始化 HashMap 需遍历 inorder ，占用 O(N) 。递归共建立 N 个节点，每层递归中的节点建立、搜索操作占用 O(1) ，因此使用 O(N) 时间。
- 空间复杂度 O(N) ： HashMap 使用 O(N) 额外空间；最差情况下（输入二叉树为链表时），递归深度达到 N ，占用 O(N) 的栈帧空间；因此总共使用 O(N) 空间。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19class Solution {
int[] preorder;
HashMap<Integer, Integer> dic = new HashMap<>();
public TreeNode buildTree(int[] preorder, int[] inorder) {
this.preorder = preorder;
for(int i = 0; i < inorder.length; i++)
dic.put(inorder[i], i);
return recur(0, 0, inorder.length - 1);
}
TreeNode recur(int root, int left, int right) {
if(left > right) return null; // 递归终止
TreeNode node = new TreeNode(preorder[root]); // 建立根节点
int i = dic.get(preorder[root]); // 划分根节点、左子树、右子树
node.left = recur(root + 1, left, i - 1); // 开启左子树递归
node.right = recur(root + i - left + 1, i + 1, right); // 开启右子树递归
return node; // 回溯返回根节点
}
}