leetcode-flatten-binary-tree-to-linked-list

题目大意

　　https://leetcode.com/problems/flatten-binary-tree-to-linked-list/

　　把一颗二叉树转换成链表，链表中的元素顺序是二叉树的前序遍历，要求空间复杂度是O(1)

题目分析

　　可以用递归来做（可能不是最优的方法）。先把左右子树分别flatten，然后利用循环把左子树的叶子节点找到，把右子树的头节点接过来。

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void flatten(TreeNode root) {
        if(root == null)    return ;
        flatten(root.left);
        flatten(root.right);
        TreeNode end = root.left;
        if(end != null) {
            while(end.right != null) {
                end = end.right;
            }
            end.right = root.right;
            root.right = root.left;
            root.left = null;
        }
    }
}