算法数据结构基础——二叉树的还原（基于遍历序列还原二叉树）_二叉树复原

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        def createTree(preorder, inorder, n):
            if n == 0:
                return None
            k = 0
            while preorder[0] != inorder[k]:
                k += 1
            node = TreeNode(inorder[k])
            node.left = createTree(preorder[1: k + 1], inorder[0: k], k)
            node.right = createTree(preorder[k + 1:], inorder[k + 1:], n - k - 1)
            return node
        return createTree(preorder, inorder, len(inorder))
1
2
3
4
5
6
7
8
9
10
11
12
13

3. 从中序与后序遍历序列构造二叉树

• 描述：已知一棵二叉树的中序遍历序列和后序遍历序列。

• 要求：构造出该二叉树。

• 注意：假设树中没有重复的元素。

3.1 从中序与后序遍历序列构造二叉树实现过程

中序遍历的顺序是：左子树 - 根节点 - 右子树。后序遍历的顺序是：左子树 - 右子树 - 根节点。

根据后序遍历的顺序，可以找到根节点位置。然后在中序遍历的结果中可以找到对应的根节点位置，就可以从根节点位置将二叉树分割成左子树、右子树。同时能得到左右子树的节点个数。

此时构建当前节点，并递归建立左右子树，在左右子树对应位置继续递归遍历进行上述步骤，直到节点为空，具体操作步骤如下：

1. 从后序遍历顺序中当前根节点的位置在 postorder[n-1]。

2. 通过在中序遍历中查找上一步根节点对应的位置 inorder[k]，从而将二叉树的左右子树分隔开，并得到左右子树节点的个数。

3. 从上一步得到的左右子树个数将后序遍历结果中的左右子树分开。

4. 构建当前节点，并递归建立左右子树，在左右子树对应位置继续递归遍历并执行上述三步，直到节点为空。

3.2 从中序与后序遍历序列构造二叉树实现代码

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
        def createTree(inorder, postorder, n):
            if n == 0:
                return None
            k = 0
            while postorder[n - 1] != inorder[k]:
                k += 1
            node = TreeNode(inorder[k])
            node.right = createTree(inorder[k + 1: n], postorder[k: n - 1], n - k - 1)
            node.left = createTree(inorder[0: k], postorder[0: k], k)
            return node
        return createTree(inorder, postorder, len(postorder))
1
2
3
4
5
6
7
8
9
10
11
12
13

4. 从前序与后序遍历序列构造二叉树

前边我们说过：已知二叉树的前序遍历序列和后序遍历序列，是不能唯一地确定一棵二叉树的。 而如果不要求构造的二叉树是唯一的，只要求构造出一棵二叉树，还是可以进行构造的。

• 描述：已知一棵二叉树的前序遍历序列和后序遍历序列。

• 要求：重构并返回该二叉树。

• 注意：假设树中没有重复的元素。如果存在多个答案，则可以返回其中任意一个。

4.1 从前序与后序遍历序列构造二叉树实现过程

我们可以默认指定前序遍历序列的第 2 个值为左子树的根节点，由此递归划分左右子序列。具体操作步骤如下：

1. 从前序遍历序列中可知当前根节点的位置在 preorder[0]。

2. 前序遍历序列的第 2 个值为左子树的根节点，即 preorder[1]。通过在后序遍历中查找上一步根节点对应的位置 postorder[k]（该节点右侧为右子树序列），从而将二叉树的左右子树分隔开，并得到左右子树节点的个数。

3. 从上一步得到的左右子树个数将后序遍历结果中的左右子树分开。

4. 构建当前节点，并递归建立左右子树，在左右子树对应位置继续递归遍历并执行上述三步，直到节点为空。

4.2 从前序与后序遍历序列构造二叉树实现代码

class Solution:
    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> TreeNode:
        def createTree(preorder, postorder, n):
            if n == 0:
                return None
            node = TreeNode(preorder[0])
            if n == 1:
                return node
            k = 0
            while postorder[k] != preorder[1]:
                k += 1
            node.left = createTree(preorder[1: k + 2], postorder[: k + 1], k + 1)
            node.right = createTree(preorder[k + 2: ], postorder[k + 1: -1], n - k - 2)
            return node
        return createTree(preorder, postorder, len(preorder))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15