41.Flatten Binary Tree to Linked List-二叉树展开为链表

题目描述：


解析：可以发现展开的顺序其实就是二叉树的先序遍历。
我们需要两步完成这道题。

1. 将左子树插入到右子树的地方
2. 将原来的右子树接到左子树的最右边节点

3. 考虑新的右子树的根节点，一直重复上边的过程，直到新的右子树为 null

   整个流程如下：
   1
   / \
   2 5
   / \ \
   3 4 6

//将 1 的左子树插入到右子树的地方
1
\
2 5
/ \ \
3 4 6
//将原来的右子树接到左子树的最右边节点
1
\
2
/ \
3 4
\
5
\
6

//将 2 的左子树插入到右子树的地方
1
\
2
\
3 4
\
5
\
6

//将原来的右子树接到左子树的最右边节点
1
\
2
\
3
\
4
\
5
\
6

……

public void flatten(TreeNode root) {
    while (root != null) { 
        //左子树为 null，直接考虑下一个节点
        if (root.left == null) {
            root = root.right;
        } else {
            // 找左子树最右边的节点
            TreeNode pre = root.left;
            while (pre.right != null) {
                pre = pre.right;
            } 
            //将原来的右子树接到左子树的最右边节点
            pre.right = root.right;
            // 将左子树插入到右子树的地方
            root.right = root.left;
            root.left = null;
            // 考虑下一个节点
            root = root.right;
        }
    }
}