题目描述
递归建立整棵二叉树:先递归创建左右子树,然后创建根节点,并让指针指向两棵子树。
样例
给定:
前序遍历是:[3, 9, 20, 15, 7]
中序遍历是:[9, 3, 15, 20, 7]
返回:[3, 9, 20, null, null, 15, 7, null, null, null, null]
返回的二叉树如下所示:
3
/ \
9 20
/ \
15 7
算法1
(dfs) $O(n)$
解题思路:前序遍历第一个节点必为根节点,故根据找到中序的该节点,并此划分左右子树,递归解决(BFS)
1.将数组设为全局变量
2.将中序数组值-下标对存入hash表
3.递归,解决边界
时间复杂度
参考文献
JAVA 代码
class Solution {
int[] preorder;
int[] inorder;
public HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
public TreeNode buildTree(int[] _preorder, int[] _inorder) {
this.preorder = _preorder;
this.inorder = _inorder;
for(int i = 0; i < inorder.length; i++){
map.put(inorder[i], i);
}
return dfs(0, preorder.length-1, 0, inorder.length-1);
}
public TreeNode dfs(int pl, int pr, int il, int ir){
if(pl > pr) return null;
TreeNode root = new TreeNode(preorder[pl]);
int k = map.get(root.val);
//root.left = dfs(pl+1, pl - il + k, il, k - 1);
//root.right = dfs(pr - il + k + 1, pr, k + 1, ir);
root.left = dfs(pl + 1, pl + k - il, il, k - 1);
root.right = dfs(pl + k - il + 1, pr, k + 1, ir);
return root;
}
}