问题描述
根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
3
/ \
9 20
/ \
15 7
解题思路
preorder 中的每个值都作为新的根结点，在 inorder 中，该值的位置确定了左右子树的界限。
-
\(\text{preorder} = [\boxed{3},9,20,15,7], \text{inorder}=[\underbrace{9}_{左子树},\underbrace{\boxed{3}}_{根结点}, \underbrace{15,20,7}_{右子树}]\)
-
\(\text{preorder} = [\boxed{9}], \text{inorder}=[\underbrace{\text{None}}_{左子树},\underbrace{\boxed{9}}_{根结点}, \underbrace{\text{None}}_{右子树}]\)
-
\(\text{preorder} = [\boxed{20},15,7], \text{inorder}=[\underbrace{15}_{左子树},\underbrace{\boxed{20}}_{根结点}, \underbrace{7}_{右子树}]\)
-
\(\text{preorder} = [\boxed{15}], \text{inorder}=[\underbrace{\text{None}}_{左子树},\underbrace{\boxed{15}}_{根结点}, \underbrace{\text{None}}_{右子树}]\)
-
\(\text{preorder} = [\boxed{7}], \text{inorder}=[\underbrace{\text{None}}_{左子树},\underbrace{\boxed{7}}_{根结点}, \underbrace{\text{None}}_{右子树}]\)
根据 \(\texttt{preorder}\) 根结点确定 \(\texttt{inorder}\) 中的根结点的位置，进而确定下一步中左右子树的范围以及根结点位置。
在先序遍历中，某个结点的 左子树的根结点 就在该结点之后，而该结点的 右子树的根结点 则在该结点加上 左子树结点数量 之后。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
index = {x: i for i, x in enumerate(inorder)}
def dfs(preorder_root: int, inorder_left: int, inorder_right: int) -> TreeNode:
if inorder_left > inorder_right: return None
root = TreeNode(preorder[preorder_root])
inorder_root = index[preorder[preorder_root]]
root.left = dfs(preorder_root + 1, inorder_left, inorder_root - 1)
root.right = dfs(preorder_root + (inorder_root - inorder_left) + 1, inorder_root + 1, inorder_right)
return root
return dfs(0, 0, len(inorder) - 1)
|
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 | class Solution {
public:
unordered_map<int, int> index;
TreeNode* dfs(vector<int> &preorder, vector<int> &inorder, int preorder_root, int inorder_left, int inorder_right) {
if (inorder_left > inorder_right) return nullptr;
auto root = new TreeNode(preorder[preorder_root]);
int inorder_root = index[preorder[preorder_root]];
root->left = dfs(preorder, inorder, preorder_root + 1, inorder_left, inorder_root - 1);
// inorder_root - inorder_left 为左子树元素个数
root->right = dfs(preorder, inorder, preorder_root + (inorder_root - inorder_left) + 1, inorder_root + 1, inorder_right);
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int n = inorder.size();
for (int i = 0; i < n; ++i) {
index[inorder[i]] = i;
}
return dfs(preorder, inorder, 0, 0, n - 1);
}
};
|
时间复杂度：\(\mathcal{O}(n)\)
空间复杂度：\(\mathcal{O}(n)\)