Thoughts on convert this question to question 105


  • 2
    J

    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]:
                stack.append(node)
                new_node = TreeNode(preorder[d1+1])
                node.right = new_node
                stack.append(new_node)
                d1 += 1
            else:
                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
                stack.append(new_node)
                
        return head

Log in to reply
 

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