难度 medium
给你二叉树的根结点 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：可以用递归的解法来解决，flatten函数用于整理当前节点，先分别对当前节点的左子节点和右子节点进行flatten，然后先把经过flatten的左节点拼到当前节点的右边，然后一直往右遍历，找到最右节点，再将经过flatten的右节点拼在最右节点的右边，最后尤其需要注意的一点是当前节点的left指针要指向null，我的思路一开始就是正确的，少了这一步莫名奇妙多了很多元素出来，后来检查了题目才想起这个。

代码 t100 s75 java

class Solution {
    public void flatten(TreeNode root) {
        if(root==null) return;
        flatten(root.right);
        TreeNode temp = root.right;
        flatten(root.left);
        root.right = root.left;
        root.left = null;
        while(root.right!=null) root = root.right;
        root.right = temp;
    }
}

解题思路2：这个解法是在grandyang的博客上看到的，不用递归，就是对当前节点，判断是否有左子树，如果有，就把它插到当前节点和右节点之间，这个插入的意思是，当前节点的right指针指向左节点，然后从左节点一直往右遍历直到到达最右节点，然后把右节点接在这个最右节点的后面，然后当前节点向右节点移动，继续上述过程。这样就把左边的节点按照规则都插到右边来了。

代码 t100 s70 java

class Solution {
    public void flatten(TreeNode root) {
        TreeNode cur = root;
        while(cur!=null){
            if(cur.left!=null){
                TreeNode p = cur.left;
                while(p.right!=null) p = p.right;
                p.right = cur.right;
                cur.right = cur.left;
                cur.left = null;
            }
            cur = cur.right;
        }
    }
}

参考资料：
https://www.cnblogs.com/grandyang/p/4293853.html