给你二叉树的根结点 root ，请你将它展开为一个单链表：

    展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
    展开后的单链表应该与二叉树 先序遍历 顺序相同。

    示例 1：

    输入：root = [1,2,5,3,4,null,6]
    输出：[1,null,2,null,3,null,4,null,5,null,6]
    示例 2：

    输入：root = []
    输出：[]
    示例 3：

    输入：root = [0]
    输出：[0]

    提示：

    树中结点数在范围 [0, 2000] 内
    -100 <= Node.val <= 100

    进阶：你可以使用原地算法（O(1) 额外空间）展开这棵树吗？

    思路：
    方法一：自下而上
    方法二：自上而下
    方法三：先序遍历存储再构造

    1. //自下而上
    2. //左右根遍历
    3. /**
    4.  * Definition for a binary tree node.
    5.  * public class TreeNode {
    6.  *     int val;
    7.  *     TreeNode left;
    8.  *     TreeNode right;
    9.  *     TreeNode() {}
    10.  *     TreeNode(int val) { this.val = val; }
    11.  *     TreeNode(int val, TreeNode left, TreeNode right) {
    12.  *         this.val = val;
    13.  *         this.left = left;
    14.  *         this.right = right;
    15.  *     }
    16.  * }
    17.  */
    18. class Solution {
    19.     public void flatten(TreeNode root) {
    20.         dfs(root);
    21.     }
    23.     void dfs(TreeNode root) {
    24.         if (root == null)
    25.             return;
    27.         dfs(root.left);
    28.         dfs(root.right);
    29.         if (root.left != null) {
    30.             TreeNode pre = root.left;
    31.             while (pre.right != null)
    32.                 pre = pre.right;
    33.             pre.right = root.right;
    34.             root.right = root.left;
    35.             root.left = null;
    36.         }
    37.     }
    38. }
    40. //右左根遍历,妙啊！
    41. class Solution {
    42.     TreeNode st;
    43.     public void flatten(TreeNode root) {
    44.         dfs(root);
    45.     }
    46.     void dfs(TreeNode root) {
    47.         if (root == null)
    48.             return;
    49.         dfs(root.right);
    50.         dfs(root.left);
    52.         root.right = st;
    53.         root.left = null;
    54.         st = root;
    55.     }
    56. }
    1. //自下而上，一种类Morris遍历
    2. class Solution {
    3.     public void flatten(TreeNode root) {
    4.         while (root != null) {
    5.             if (root.left != null) {
    6.                 TreeNode pre = root.left;
    7.                 while (pre.right != null)
    8.                     pre = pre.right;
    9.                 pre.right = root.right;
    10.                 root.right = root.left;
    11.                 root.left = null;
    12.             }
    13.             root = root.right;
    14.         }
    15.     }
    16. }