114. 二叉树展开为链表

题目链接

114. 二叉树展开为链表

题目

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

• 展开后的单链表应与二叉树 先序遍历 顺序相同。
• 展开后的单链表应由树中的 原地 节点（即不新开辟额外的节点）组成。

思路

我们需要将二叉树按照前序遍历的顺序展开为链表形式。最优的解法是通过原地修改的方式，不需要额外的空间，时间复杂度也保持在 $O(n)$。

步骤如下：

1. 从根节点开始进行遍历，如果当前节点的左子树不为空，则找到左子树的最右边的节点（即前序遍历中的前驱节点）。
2. 将当前节点的右子树移动到前驱节点的右子树上。
3. 然后将左子树作为当前节点的右子树，并将当前节点的左子树置空。
4. 继续处理右子树，直到所有节点处理完毕。

这个方法利用了树的前驱节点，并且可以在原地将树修改为链表形式。

代码

var flatten = function(root) {
    let curr = root;

    while (curr !== null) {
        if (curr.left !== null) {
            // 找到左子树的最右节点
            let next = curr.left;
            let predecessor = next;
            while (predecessor.right !== null) {
                predecessor = predecessor.right;
            }
            // 将当前节点的右子树接到前驱节点的右子树上
            predecessor.right = curr.right;
            // 将左子树作为当前节点的右子树
            curr.right = next;
            curr.left = null;
        }
        // 移动到下一个节点
        curr = curr.right;
    }
};

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 为二叉树的节点数。每个节点我们只访问一次，且在处理前驱节点时最多只访问每个节点两次。
• 空间复杂度：$O(1)$，因为我们是原地修改的，没有使用额外的空间。