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

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

  • 标签:树、数组、哈希表、分治、二叉树
  • 难度:中等

题目大意 #

给定一棵二叉树的中序遍历结果和后序遍历结果,然后构造出该二叉树。假设树中没有重复的元素。

解题思路 #

中序遍历的顺序是:左 -> 根 -> 右。后序遍历的顺序是:左 -> 右 -> 根。根据后序遍历的顺序,可以找到根节点位置。然后在中序遍历的结果中可以找到对应的根节点位置,就可以从根节点位置将二叉树分割成左子树、右子树。同时能得到左右子树的节点个数。此时构建当前节点,并递归建立左右子树,在左右子树对应位置继续递归遍历进行上述步骤,直到节点为空,具体操作步骤如下:

  • 从后序遍历顺序中当前根节点的位置在 postorder[n-1]
  • 通过在中序遍历中查找上一步根节点对应的位置 inorder[k],从而将二叉树的左右子树分隔开,并得到左右子树节点的个数。
  • 从上一步得到的左右子树个数将后序遍历结果中的左右子树分开。
  • 构建当前节点,并递归建立左右子树,在左右子树对应位置继续递归遍历并执行上述三步,直到节点为空。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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))
本站总访问量  次  |  您是本站第  位访问者