Leetcode 114: Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place.

For example,
Given

         1
        / \
       2   5
      / \   \
     3   4   6

The flattened tree should look like:

   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

 

Code

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def __init__(self):
        self.prev = None
        
    def flatten(self, root):
        """
        :type root: TreeNode
        :rtype: void Do not return anything, modify root in-place instead.
        """
        if root is None: return
        self.flatten(root.right)
        self.flatten(root.left)
        # self.prev is root's left subtree's root
        root.right = self.prev
        root.left = None
        self.prev = root   

 

Idea

Create a variable self.prev, which records the current node (root)’s left subtree’s root. Overall it utilizes a post-order traversal. The algorithm first traverses right subtree then left subtree and finally adjusts the current root’s left and right subtree.

Reference: https://discuss.leetcode.com/topic/11444/my-short-post-order-traversal-java-solution-for-share/2

 

Code

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def flatten(self, root):
        """
        :type root: TreeNode
        :rtype: void Do not return anything, modify root in-place instead.
        """
        while root:
            ln = root.left
            if ln is not None:
                # find the right-most element of the left subtree 
                while ln.right:
                    ln = ln.right
                ln.right = root.right
                root.right = root.left
                root.left = None
            root = root.right

 

Idea

Iterative way. Time complexity is O(n) since every node can be set as root and ln no more than once.

Reference: https://discuss.leetcode.com/topic/3995/share-my-simple-non-recursive-solution-o-1-space-complexity