Thoughts on convert this question to question 105

  • 2

    If we totally reverse the post-order traverse (new_traverse = postorder[::-1]), it becomes a 'pre-order' traverse that visit father->right child-> left child

    Similarly, if we reverse in-order traverse, it becomes a 'in-order' traverse that visit right->father->left.

    Then, these two new traverse is the same as the traverse in question 105. The only difference is that left becomes right and right becomes left. We can use same method in 105 to solve it. Below is a sample of iterative solution. Hope this helps.

    class Solution(object):
    def buildTree(self, inorder, postorder):
        :type inorder: List[int]
        :type postorder: List[int]
        :rtype: TreeNode
        inorder = inorder[::-1]
        preorder = postorder[::-1]
        if preorder == []:
            return None
        d1,d2 = 0,0
        head = TreeNode(preorder[0])
        stack = [head]
        while d1 < len(preorder)-1:
            node = stack.pop()
            if node.val != inorder[d2]:
                new_node = TreeNode(preorder[d1+1])
                node.right = new_node
                d1 += 1
                while stack != [] and stack[-1].val == inorder[d2+1]:
                    node = stack.pop()
                    d2 += 1
                d2 +=1
                d1 +=1
                new_node = TreeNode(preorder[d1])
                node.left = new_node
        return head

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.