An inorder python solution


  • 14
    J
    class Solution:
    # @param root, a tree node
    # @return nothing, do it in place
    prev = None
    def flatten(self, root):
        if not root:
            return
        self.prev = root
        self.flatten(root.left)
    
        temp = root.right
        root.right, root.left = root.left, None
        self.prev.right = temp
    
        self.flatten(temp)
    
    
    
             *
           /
          n
       /     \
     left   right
      \ 
       *
        *
         \
          p
    

    The idea is very simple. Suppose n is the current visiting node, and p is the previous node of preorder traversal to n.right.

    We just need to do the inorder replacement:

    n.left -> NULL

    n.right - > n.left

    p->right -> n.right


  • 0
    B

    I think this is a very smart method. i was wondering how to solve this problem recursively and didn't know how to return the 'prev'. very helpful, thanks a lot.


  • 7
    D

    I think there is no need to pass prev. See my code and embedded comments

    class Solution:
        # @param {TreeNode} root
        # @return {void} Do not return anything, modify root in-place instead.
        def flatten(self, root):
            '''
            1. flatten left subtree
            2. find left subtree's tail
            3. set root's left to None, root's right to root'left, tail's right to root.right
            4. flatten the original right subtree
            '''
            # escape condition
            if not root:
                return
            right = root.right
            if root.left:
                # flatten left subtree
                self.flatten(root.left)
                # find the tail of left subtree
                tail = root.left
                while tail.right:
                    tail = tail.right
                # left <-- None, right <-- left, tail's right <- right
                root.left, root.right, tail.right = None, root.left, right
            # flatten right subtree
            self.flatten(right)

  • 0
    H

    @dasheng2

    while tail.right:
        tail = tail.right
    

    this code will loop over left subtree, which waste a lot of time


  • 0
    D

    @julian3
    Hi Julian, I am a little bit confused about how do you get self.prev to the end of left side.


Log in to reply
 

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