Annotated iterative solution with comments, does not modify parameters


  • 2

    Courtesy of the post by lizhuogo. Details see
    https://discuss.leetcode.com/topic/4746/my-comprehension-of-o-n-solution-from-hongzhi/2

    I thought his explanation is still a bit difficult to understand so I try to give a high-level understanding of this approach and the fundamental reason why it works as intended.

    The key here is knowing the patterns of serialized list of inorder and postorder
    travesals.

    If we traverse from root to the left child and back up, both inorder
    and postorder traversals give us the same sequence, i.e. they are in
    the same direction.

           1
          /
        2
    inorder:  [1, 2]
    postorder: [1, 2]
    

    whereas if we traverse from root to right child and back up, inorder and postorder
    gives us sequences that are reverse of each other.

         1
          \
           2
    inorder: [1, 2]
    postorder: [2, 1]
    

    Using this observation, and the fact that the last member in postorder array is
    the root of current subtree, we can traverse from right to left of the serialized
    lists and build left and right child accordingly.

    If we see postorder and inorder are of same value, we build the left child, else
    we build the right child. After each operation, we store the newly created node
    on stack to be the new root of the current subtree of size 1 and later traverse back
    up.

    A stack is helpful for storing them because each pop let us go back up a level to
    the parent of our current root.

    Code in Python below with comments:

    def buildTree(self, inorder, postorder):
        if len(inorder) == 0: return None
        root = TreeNode(postorder[-1])
        stack = [root]   
        # array indexes, i for inorder array, p for postorder array
        i = len(inorder) - 1
        p = len(postorder) - 2 # initially root already 'popped' off postorder and stored in stack
    
        # we store values off postorder array and compare top of stack with
        # right most member of inorder array (indexed by i)
        while True:
          # top of stack is same as right most entry of inorder. The first time it
          # happens means we reached root of current tree. Then we keep removing them
          # since we already built right child nodes with them and they are on stack just so we
          # can traverse back up. See the else branch for the actual creation of right child. 
          if stack[-1].val == inorder[i]:
            n = stack.pop()
            i -= 1
    
            if i==-1: break
            if stack and inorder[i] == stack[-1].val:
              # keep removing these values, that is, traverse back up
              continue
    
            # finished all the right branch and root itself, now we build left child
            # 'n' here was popped from stack which gave us the current root.
            n.left = TreeNode(postorder[p])
            p -= 1
            stack.append(n.left)
    
          else: # mismatch values means we should build right child for current root
            n = TreeNode(postorder[p])
            p-=1
            stack[-1].right = n
            stack.append(n)
            
        return root
    

Log in to reply
 

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