二叉树展开为链表的算法解析与实现

将二叉树展开为链表是一个常见的算法问题，通常要求将二叉树按照前序遍历的顺序展开为一个单链表。展开后的链表应该使用二叉树的右指针来连接节点，左指针应该全部置为 null。

问题描述

给定一个二叉树，将其展开为一个单链表。展开后的链表应该使用二叉树的右指针来连接节点，左指针应该全部置为 null。

示例

输入:
    1
   / \
  2   5
 / \   \
3   4   6

输出:
1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

解决方案

我们可以使用递归或迭代的方法来解决这个问题。以下是两种常见的解决方案：

方法一：递归

1. 前序遍历：首先对二叉树进行前序遍历，将节点按顺序存储在一个列表中。
2. 重构链表：遍历列表，将每个节点的右指针指向下一个节点，左指针置为 null。

function flatten(root) {
    if (!root) return;

    // 前序遍历，将节点存储在列表中
    const nodes = [];
    preOrder(root, nodes);

    // 重构链表
    for (let i = 0; i < nodes.length - 1; i++) {
        nodes[i].left = null;
        nodes[i].right = nodes[i + 1];
    }
}

function preOrder(node, nodes) {
    if (!node) return;
    nodes.push(node);
    preOrder(node.left, nodes);
    preOrder(node.right, nodes);
}

方法二：迭代（使用栈）

1. 使用栈模拟前序遍历：通过栈来模拟前序遍历的过程。
2. 重构链表：在遍历过程中，将当前节点的右指针指向栈顶节点，左指针置为 null。

function flatten(root) {
    if (!root) return;

    const stack = [root];
    let prev = null;

    while (stack.length) {
        const curr = stack.pop();

        if (prev) {
            prev.left = null;
            prev.right = curr;
        }

        if (curr.right) stack.push(curr.right);
        if (curr.left) stack.push(curr.left);

        prev = curr;
    }
}

方法三：原地修改（O(1) 空间复杂度）

1. 找到左子树的最右节点：对于每个节点，找到其左子树的最右节点。
2. 将右子树接到最右节点：将当前节点的右子树接到左子树的最右节点上。
3. 将左子树移到右子树：将左子树移到右子树的位置，左指针置为 null。

function flatten(root) {
    let curr = root;
    while (curr) {
        if (curr.left) {
            let prev = curr.left;
            while (prev.right) {
                prev = prev.right;
            }
            prev.right = curr.right;
            curr.right = curr.left;
            curr.left = null;
        }
        curr = curr.right;
    }
}

复杂度分析

• 时间复杂度：O(N)，其中 N 是二叉树的节点数。每个节点被访问一次。
• 空间复杂度：
  • 方法一和方法二：O(N)，需要存储所有节点。
  • 方法三：O(1)，只使用了常数级别的额外空间。

总结

将二叉树展开为链表可以通过多种方法实现，具体选择哪种方法取决于对空间复杂度的要求。如果允许使用额外的空间，递归和迭代的方法都比较直观。如果要求原地修改，方法三是最优的选择。