zhengsl's Blog
根据前、中、后序数组构造二叉树

Photo by Hu Chen on Unsplash

根据前、中、后序数组构造二叉树

zhengsl's photo
zhengsl
·

2 min read

Table of contents

根据两个遍历数组生成二叉树，主要是固定住一个根节点，然后去另一个数组查找下标，划分数组做左右子树，再递归执行左子树和右子树。

这里主要讨论的是使用切片的过程中如何确定切片的起始点，即切片的区间，利用的是左子树的长度。

前序和中序构造二叉树

105. 从前序与中序遍历序列构造二叉树

递归加切片， python 中可以使用 index 函数直接获取值的下标。 注意：切片是左闭右开区间，最后一个值取不到

切片的下标如何思考：利用左子树的长度来辅助思考。idx 是中序数组中的当前节点下标，所以左子树长度是 idx，所以中序数组分成左右两个数组 [1,idx], [idx+1,-1]，其中 [1,idx] 的长度是 idx-1+1= idx。因为切片是左闭右开的，因此分成 [1,idx+1) 和 [idx+1,-1] 两个区间。中序数组就简单了，以 idx 为界分成左右两个区间 [0,idx), [idx+1,-1]，因为 idx 已经被用了，因此两个区间都不包含 idx 下标。

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        def dfs(preorder: List[int], inorder: List[int]):
            if len(preorder) == 0 or len(inorder) == 0:
                return None
            root = TreeNode(preorder[0])
            idx = inorder.index(preorder[0])
            root.left = dfs(preorder[1:idx+1], inorder[:idx])
            root.right = dfs(preorder[idx+1:], inorder[idx+1:])
            return root
        return dfs(preorder, inorder)

中序和后序构造二叉树

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

image-20221009201059977

image-20221009201117876

在没有切片的语言中需要重新定义一个函数，然后定义前序、中序、后序的的起始点和终止点，然后迭代！Go 语言有切片，直接传递切片即可！

如何思考切片下标？ 还是利用左子树长度来辅助思考。idx 是中序遍历当前节点下标，左子树长度就是 idx。中序数组比较简单，idx 节点已经使用了，中序数组以 idx 为界分成左右两个区间 [0,idx)，[idx+1,-1]。后序数组中左子树长度 idx，因此分成两个数组 [0,idx) 和 [idx,-1) ，其中 [0,idx) 的长度也是 idx。

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        def dfs(inorder: List[int], postorder: List[int]):
            if not (len(inorder) > 0 and len(postorder) > 0):
                return None
            root = TreeNode(postorder[-1])
            idx = inorder.index(postorder[-1])
            root.left = dfs(inorder[:idx], postorder[:idx])
            root.right = dfs(inorder[idx+1:], postorder[idx:-1])
            return root
        return dfs(inorder, postorder)

前序和中序构造二叉树

889. 根据前序和后序遍历构造二叉树

  • 前序和后序无法唯一确定一棵二叉树，因此写出一种即可

  • 将前序数组的第二个值作为左子树的根节点，在后序数组中找到这个根节点，这个节点的左侧包括这个节点即左子树，右侧即右子树！

image-20221009204424097

  • 左右子树无法确定的原因在于：if preorder[1] == postorder[i] 将先序数组的第二个元素作为左子树，但第二个元素有可能是右子树的根节点，左子树根节点为空！

如何确定切片的下标呢？还是借助左子树长度来辅助思考。前序数组的第一个值和后序数组的最后一个值是相同的，做当前节点值。假设前序数组的第二个值是左子树根节点，则在后序数组中找到这个值的下标，因为这个值属于左子树，因此左子树的长度是[0:idx] 数组的长度 idx+1。所以前序数组可以分成 [1,idx+2) 和 [idx+2,-1] 两个数组，其中 [1,idx+2) 的长度是 idx+1。后序数组就可以分成 [0,idx+1), [idx+1,-1] 两个数组，其中 [0,idx+1) 的长度是 idx+1

class Solution:
    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        def dfs(preorder: List[int], postorder: List[int]):
            if len(preorder)==0:
                return None
            if len(preorder) == 1:
                return TreeNode(preorder[0])
            root = TreeNode(preorder[0])
            left_val = preorder[1]
            idx = postorder.index(left_val)
            root.left = dfs(preorder[1:idx+2], postorder[:idx+1])
            root.right = dfs(preorder[idx+2:], postorder[idx+1:-1])
            return root
        return dfs(preorder, postorder)
二叉树