二叉树展开为链表

114.二叉树展开为链表

题意

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

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

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

思路一：先序遍历

如题，展开的顺序其实就是二叉树的先序遍历。先序遍历的访问顺序是 “根、左子树、右子树”，左子树最后一个节点访问完后，接着会访问根节点的右子树节点。

• 将左子树插入到右子树的地方
• 将原来的右子树接到左子树的最右边节点
• 考虑新的右子树的根节点，一直重复上边的过程，直到新的右子树为 null.

时间复杂度 $O(n)$，其中 $n$ 是树中节点的个数。空间复杂度 $O(1)$。

代码：

class Solution {
    public void flatten(TreeNode root) {
        while (root != null) {
            if (root.left != null) {
                // 找到当前节点左子树的最右节点
                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;
        }
    }
}

思路二：递归

尝试直接在原来的节点上改变指向，利用先序遍历的代码，每遍历一个节点，就将上一个节点的右指针更新为当前节点。

发现，如果这样做，原本的右子树就丢失了。

用递归的思维，要解决这个问题的话，可以逆过来进行。逆序遍历，每遍历一个节点就将当前节点的右指针更新为上一个节点。这样就不会有丢失子树的问题了，因为更新当前的右指针的时候，当前节点的右子树已经访问过了。

即使用变形后的后序遍历，遍历顺序是 右子树->左子树->根节点。这里我们不再打印根节点，而是利用一个全局变量 pre，更新当前根节点的右指针为 pre，左指针为 null.

代码：

class Solution {
    TreeNode pre = null;

    public void flatten(TreeNode root) {
        if (root == null) return;

        flatten(root.right);
        flatten(root.left);

        root.right = pre;
        root.left = null;
        pre = root;
    }
}