Skip to content

106 construct binary tree from inorder and postorder traversal

106. Construct Binary Tree from Inorder and Postorder Traversal

题目: https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/

难度 : Medium

inorder 是 左 -> 根 -> 右 postorder 是 左 -> 右 -> 根

跟105基本一样

还是先弄了一个递归可用版本

def buildTree(inorder, postorder):
    """
    :type preorder: List[int]
    :type inorder: List[int]
    :rtype: TreeNode
    """
    if postorder == inorder == []:
        return None
    else:
        rootVal = postorder[-1]
        root = TreeNode(rootVal)
        k = inorder.index(rootVal)
        root.left = buildTree(inorder[:k],postorder[:k])
        root.right = buildTree(inorder[k+1:],postorder[k:-1])
        return root

照抄105

class Solution(object):
    def buildTree(self, inorder, postorder):
        """
        :type inorder: List[int]
        :type postorder: List[int]
        :rtype: TreeNode
        """
        def buildTree(inorder, postorder, li, ri ,lp, rp ):
            if lp > rp or li > ri:
                return None

            root = TreeNode(postorder[rp])
            k = inorder.index(postorder[rp])

            # left node
            left = buildTree(inorder, postorder, li, k-1, lp, lp + k - li - 1)
            right = buildTree(inorder, postorder, k+1, ri, lp+k-li, rp-1)

            root.left = left
            root.right = right

            return root

        return buildTree(inorder, postorder, 0, len(inorder) - 1, 0, len(postorder) - 1)



回到顶部