Python easy to understand recursive solution with explaination.


  • 0
    C

    We can solve this problem recursively, suppose we already flattened the left part of the root, then we need set it as the right child of the root (the previous right child of the root should be preserved first by using a temp variable before this operation), after that, the previous right child is connected to the right most of the flattened left child. Don't forget to set the left child of root to None after these operations.

    def flatten(self, root):
        while root:
            if root.left:
                self.flatten(root.left)
                node1 = root.left
                while node1.right:
                    node1 = node1.right
                node2 = root.right
                root.right = root.left
                root.left = None
                node1.right = node2
            root = root.right

  • 0
    C

    The code above can be revised as below, which is more readable:

    def flatten(self, root):
        while root:
            if root.left:
                self.flatten(root.left)
                tail = root.left
                while tail.right:
                    tail = tail.right
                tail.right = root.right
                root.right = root.left
                root.left = None
            root = root.right

Log in to reply
 

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