https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal
前序遍历结果特点：root|左子树|右子树
中序遍历结果特点：左子树|root|右子树
后序遍历结果特点：左子树|右子树|root
通过中序遍历判断左右子树的节点数！
通过前序遍历和中序遍历还原二叉树
1
2
3
4
5
6
7
8
9
10
| def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
def build(pre_start, in_start, in_end):
if pre_start < len(preorder) and in_start <= in_end:
cur = inorder.index(preorder[pre_start])
left = build(pre_start + 1 , in_start, cur - 1)
right = build(pre_start + (cur - in_start) + 1, cur + 1 , in_end)
return TreeNode(preorder[pre_start], left, right)
return build(0, 0, len(inorder) - 1)
|
通过中序遍历和后续遍历还原二叉树
1
2
3
4
5
6
7
8
9
10
| def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
def build(post_end, in_start, in_end):
if post_end >= 0 and in_start <= in_end:
cur = inorder.index(postorder[post_end])
left = build(post_end - (in_end - cur) - 1, in_start, cur - 1)
right = build(post_end - 1 , cur + 1 , in_end)
return TreeNode(postorder[post_end], left, right)
return build(len(postorder) - 1, 0, len(inorder) - 1)
|
通过前序遍历和后续遍历不能100%还原二叉树，只能求出可能的情况