/**
1. 将左右子树都转移到右子树上形成一条链, 关键的问题是把左子节点赋值给右子节点时, 怎么保存右子节点
2. 看一下先序遍历, 右子树应该接到左子树的最右的右儿子上
3. 注意要把左儿子置为null
*/

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