Flatten Binary Tree to Linked List

依旧从递归的思想入手，这里分治法可以这样考虑：

• 假设左右子树已经排列好了，如何进行合并 问题在于如何获得左子树的最后最右节点（以接上右子树），最简单直接的方法，通过一个while不断去取左子树的最后一个节点。 这个题目是很典型的树的子问题。先递归还是后递归取决于递归函数的定义，所以一定要把递归函数的定义先想清楚了。

public class Solution {
    public void flatten(TreeNode root) {
        if(root == null) return;

        flatten(root.left);
        flatten(root.right);

        TreeNode left = root.left;
        TreeNode right = root.right;

        root.left = null;
        root.right = left;
        while(root.right != null){
            root = root.right;
        }
        root.right = right;
    }
}

美中不足是每次都要把左子树遍历一遍好去找尾端节点，如果整个树左子树体积非常大而右子树很小的话，时间复杂度会很高。最差的情况是，整个树是一个只有左边的链表，时间复杂度可以达到 O(n^2)，而且用递归还要花费栈空间。

可以通过一个pre全局变量保存前一个点，这样就不需要重新while，时间复杂度可以降为O(n)