题目 二叉树展开为链表

给你二叉树的根结点 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) 额外空间）展开这棵树吗？

解法一 逆向前序遍历

用根右左的顺序遍历

先将右子树保存到栈中（每层递归保存一层，递归本身就用了每层一栈的思想）

再将左子树移动到右子树的位置覆盖掉。

class Solution {
    // 因为需要保存NULL节点，这里用LinkedList的Deque实现（关联八股）
    private Deque<TreeNode> queue = new LinkedList<>();

    public void flatten(TreeNode root) {
        if (root == null) return;
        // 根右（存）左
        dfs(root);
    }
    private TreeNode dfs(TreeNode root) {
        if (root.left == null && root.right == null) return root;
        queue.offerLast(root.right);
        root.right = root.left;
        root.left = null;
        if (root.right != null) root = dfs(root.right);
        TreeNode tempNode = queue.pollLast();
        if (tempNode == null) return root;
        root.left = tempNode;
        return dfs(root);
    }
}

时间复杂度为O(N)

空间复杂度，因为需要一个栈来保存右子树信息，最大为树的高度，也就是O(logN)

优化 – 利用每个递归自己的递归栈

我们直接把保存右子树的栈优化掉，直接通过递归栈来保存遍历状态。

从而优化掉了显式的栈使用。

class Solution {
    public void flatten(TreeNode root) {
        if (root == null) return;
        // 根右（存）左
        dfs(root);
    }
    private TreeNode dfs(TreeNode root) {
        if (root.left == null && root.right == null) return root;
        // 不用栈保存而是先挂到左子树上
        TreeNode tempNode = root.right;
        root.right = root.left;
        root.left = null;
        if (root.right != null) root = dfs(root.right);
        // 右子树（原本的左子树）遍历完毕，在进行
        if (tempNode != null) {
            root.left = tempNode;
            root = dfs(root);
        }
        return root;
    }
}

时间复杂度： O(n) 

空间复杂度：虽然最大限度地利用了递归栈，避免了显式栈的空间开销。但空间复杂度仍然是O(log n)，实际上只要涉及到树的递归遍历，一定会有递归栈来保存递归信息。要想达到O(n)的空间复杂度，就不能使用递归。

解法二 

虽然解法一及其优化时间空间复杂度已经很优秀了，但是题目中要求用O(1)的空间复杂度，也就是要求纯原地操作🥹。这里参考题解给出的一种非递归方法——寻找节点右子树的前驱节点，也就是左子树最右的节点，将右子树接过去。

class Solution {
    public void flatten(TreeNode root) {
        TreeNode curNode = root;
        while (curNode != null) {
            if (curNode.left != null) {
                // 找左子树的最右节点
                TreeNode leftNode = curNode.left;
                curNode.left = null;
                TreeNode preNode = leftNode;
                while (preNode.right != null) preNode = preNode.right;
                preNode.right = curNode.right;
                curNode.right = leftNode;
            }
            curNode = curNode.right;
        }
    }
}

时间复杂度 O(N)

空间复杂度 O(1)