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

把Tree变成LinkedList，我们需要一个额外的变量记录上一次变化到那个点，这样对于当前点，我们才能将它连接到上一个点。

public class Solution {
    //Time: O(n)
    private TreeNode last = null;
    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        
        if (last != null) {
            last.left = null;
            last.right = root;
        }
        
        last = root;
        TreeNode right = root.right;
        flatten(root.left);
        flatten(right);
    }
}