114 二叉树展开为链表

题目：
给定一个二叉树，原地将它展开为一个单链表。

例如，给定二叉树

    1
   / \
  2   5
 / \   \
3   4   6
将其展开为：

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

思路：
采用递归的思路来解决问题。递归的特点就在于，无需关注函内部数处理的细节，只需要关注函数的功能以及函数的输入输出即可。
对于这道题而言，可以分三步解决问题：

1. 将左子树展开为链表
2. 将右子树展开为链表
3. 将链表形式的右子树放在链表形式的左子数的右边

代码：

class Solution {
    public void flatten(TreeNode root) {
        if(root == null)
            return;
        //先分别将左右子数转化为链表
        flatten(root.left);
        flatten(root.right);
        //先把root.right保存下来，再将左子树接到root.right上来，之后把root.left置空
        TreeNode temp = root.right;
        root.right = root.left;
        root.left = null;
        TreeNode cur = root;
        //将右子数接到当前链表的末尾
        while(cur.right != null)
            cur = cur.right;
        cur.right = temp;
    }
}