[Leetcode] Flatten Binary Tree to Linked List

Problem

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

Algorithm

When related to tree, first consider recursive algorithm. 

Use Result Class

Recursively flatten the left subtree and right subtree, then append them to the root. The key point is how to append the flatten subtrees. What do we need to append the subtrees? 

1. Root

2. Head of the flatten left subtree

3. Tail of the flatten left subtree

4. Head of the flatten right subtree

Since the method can only has one return value. We create a HeadTail class, which stores both the head and tail of a flatten tree. With this helper class, we can easily append flatten left subtree to root.right and append head of flatten right subtree to left's tail. 

Preorder Traversal

The flatten tree is actually a preorder traversed linked list of the tree. So, naturally, the recursive preorder traversal algorithm may help. Recall the recursive preorder traversal algorithm 

preorder (root){

  if(root == null) return

  print(root)

  preorder(root.left)

  preorder(root.right)

}

Whenever, we discover a node in the preorder traversal, we append it to the tail of the linked list. Remember to set the left child to be null. 

Code