根据一棵树的前序遍历与中序遍历构造二叉树。
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 = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树:
3
/ \
9 20
/ \
15 7
由两种遍历结果还原二叉树,是一种很经典的面试题型。其中中序遍历结果必须为已知才能还原二叉树。
本题为前序中序还原二叉树,回顾一下遍历顺序:
看中序遍历,找到根结点,一定可以分成左右子树。例如二叉树:
3
/ \
9 20
/ \
15 7
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
前序遍历第一个结点 3 ,就是根结点,找到中序遍历中结点值为 3 的位置:
中序遍历 inorder = [9,3,15,20,7]
^
以 3 为根结点划分两个左右子树:
3
/ \
[9] [15,20,7]
前序遍历第二个结点 9,就是下一个子树的根结点,找到中序遍历中结点值为 9 的位置:
中序遍历 inorder :
3
/ \
[9] [15,20,7]
^
结点 9 为叶子结点,不可再划分:
3
/ \
9 [15,20,7]
前序遍历第三个结点 20,就是下一个子树的根结点,找到中序遍历中结点值为 20 的位置:
中序遍历 inorder :
3
/ \
9 [15,20,7]
^
以 20 为根结点划分两个左右子树:
3
/ \
9 20
/ \
[15] [7]
前序遍历第三个结点 15,就是下一个子树的根结点,找到中序遍历中结点值为 15 的位置:
……
由此可知中序遍历必须为已知条件才可找出出每个子树的根结点。
Java:
class Solution {
int[] preorder;
int[] inorder;
int index_pre = 0;
HashMap<Integer, Integer> index_Map = new HashMap<>();
public TreeNode buildTree(int[] preorder, int[] inorder) {
this.preorder = preorder;
this.inorder = inorder;
// 将中序遍历结果的结点值与索引位置映射
for (int i = 0; i < inorder.length; i++)
index_Map.put(inorder[i], i);
return helper(0, inorder.length - 1);
}
private TreeNode helper(int left, int right) {
// 基线条件
if (left > right)
return null;
// 按顺序逐个取前序遍历结果,并构造为根结点
int root_val = preorder[index_pre++];
TreeNode root = new TreeNode(root_val);
// 查找该根结点在中序遍历中的索引位置
int index_in = index_Map.get(root_val);
// 构造递归
root.left = helper(left, index_in - 1);
root.right = helper(index_in + 1, right);
return root;
}
}
Python:
Python 中也可以将 index_pre
提升到全局变量,这里为了结构上的整齐,使用的是 nonlocal
关键字。
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
def helper(left=0, right=len(inorder)-1):
nonlocal index_pre
# 基线条件
if left > right:
return None
# 按顺序逐个取前序遍历结果,并构造为根结点
root_val = preorder[index_pre]
root = TreeNode(root_val)
# 查找该根结点在中序遍历中的索引位置
index_in = index_map[root_val]
# 构造递归
index_pre += 1
root.left = helper(left, index_in-1)
root.right = helper(index_in+1, right)
return root
index_pre = 0
# 将中序遍历结果的结点值与索引位置映射
index_map = {val: index for index, val in enumerate(inorder)}
return helper()