根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
3
/
9 20
/
15 7
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解：
此题跟上一道题，根据后序遍历和中序遍历构造二叉树思路基本一致。
- 存储中序遍历的节点 和 下标对应的map
- 前序遍历首元素为二叉树的根节点，找到根节点，在map中找到下标
- 中序遍历遍历顺序为 根节点 左 右 , 所以根节点的左子树为[0, idx - 1]. 右子树为[idx + 1,end].
- 分别构建左右子树
代码如下：
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
28
29
30
31
32
33
|
HashMap<Integer,Integer> map = new HashMap<>(); // 用于存放中序遍历的 元素 -> 下标对应的字典
int rootIdx = 0; // 存放前序遍历的数组中，root的下标
int[] preorder = null; // 全局化 前序遍历数组
private TreeNode buildTreeHelper(int startIdx, int endIdx){
if (startIdx > endIdx) return null;
TreeNode root = new TreeNode(preorder[rootIdx]);
int idx = map.get(preorder[rootIdx]);
rootIdx ++;
// 左子树
root.left = buildTreeHelper(startIdx,idx - 1);
// 右子树
root.right = buildTreeHelper(idx + 1, endIdx);
return root;
}
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (inorder.length == 0 || preorder.length == 0 || inorder.length != preorder.length) return null;
if (inorder.length == 1) return new TreeNode(inorder[0]);
for (int i = 0; i < inorder.length; i++) {
map.put(inorder[i],i);
}
this.preorder = preorder;
return buildTreeHelper(0,preorder.length - 1);
}
|
复杂度分析：
时间复杂度： O(N), 递归N次，其中N为节点个数
空间复杂度：O(N), 使用递归，需要额外的栈空间，由于栈的深度为N，故空间复杂度为 O(N).