algorithms►leetcode

020-二叉树展开为链表（递归）

二叉树展开为链表

问题描述

给定一个二叉树的根节点 root，要求将二叉树 原地（in-place） 展开为一个 单链表，展开后的单链表应该与二叉树的 先序遍历 顺序相同，且每个节点的 右子指针 指向链表中的下一个节点，左子指针始终为 null。

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
输入:
    1
   / \
  2   5
 / \   \
3   4   6

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

方法一：递归展开（非原地）

思路

  1. 先序遍历 二叉树，将节点按顺序存入一个列表。
  2. 遍历列表，将每个节点的左指针设为 null，右指针指向下一个节点。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var flatten = function(root) {
    if (!root) return;
    
    const nodes = [];
    const preorder = (node) => {
        if (!node) return;
        nodes.push(node);
        preorder(node.left);
        preorder(node.right);
    };
    
    preorder(root); // 先序遍历，存储节点
    
    for (let i = 0; i < nodes.length - 1; i++) {
        nodes[i].left = null;
        nodes[i].right = nodes[i + 1];
    }
};

复杂度分析

  • 时间复杂度：O(n)，遍历所有节点两次（先序遍历 + 链表构建）。
  • 空间复杂度：O(n)，需要存储所有节点。

方法二：原地展开（递归）

思路

  1. 递归展开左右子树。
  2. 将左子树插入到右子树的位置，并 将原来的右子树接在左子树的最右节点。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var flatten = function(root) {
    if (!root) return;
    
    flatten(root.left);  // 展开左子树
    flatten(root.right); // 展开右子树
    
    const left = root.left;
    const right = root.right;
    
    root.left = null;    // 左指针置空
    root.right = left;   // 将左子树作为右子树
    
    // 找到当前右子树（原左子树）的最右节点
    let p = root;
    while (p.right) {
        p = p.right;
    }
    p.right = right;    // 将原右子树接在后面
};

复杂度分析

  • 时间复杂度：O(n)，每个节点被访问一次。
  • 空间复杂度：O(h)，递归栈的深度（h 为树高）。

方法三：原地展开（迭代 + Morris遍历）

思路

利用 Morris遍历 的思想，在遍历过程中直接修改指针，避免递归栈空间。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var flatten = function(root) {
    let curr = root;
    while (curr) {
        if (curr.left) {
            // 找到左子树的最右节点
            let predecessor = curr.left;
            while (predecessor.right) {
                predecessor = predecessor.right;
            }
            
            // 将右子树接到左子树的最右节点
            predecessor.right = curr.right;
            // 将左子树移到右子树位置
            curr.right = curr.left;
            curr.left = null;
        }
        curr = curr.right;
    }
};

复杂度分析

  • 时间复杂度：O(n)，每个节点被访问最多两次。
  • 空间复杂度：O(1)，仅使用常数级额外空间。

分步图解（以示例二叉树为例）

初始二叉树
1
2
3
4
5
     1
   /   \
  2     5
 / \     \
3   4     6
步骤 1：初始化
  • curr 指向根节点 1。
  • 检查 curr.left（2）存在，进入处理逻辑。
步骤 2：找到左子树的最右节点
  • predecessor 从 2 开始，向右走到 4（因为 4.right 为 null）。
1
2
3
4
5
6
7
8
     1
   /   \
  2     5
 / \     \
3   4     6
     ^
     |
 predecessor
步骤 3：重组指针

1.将右子树（5）挂到 predecessor 的右指针：

1
2
3
4
5
6
7
8
9
10
     1
   /   
  2     
 / \     
3   4
     \ 
      5
       \
        6

2. **将左子树（`2`）移到 `curr` 的右指针，左指针置空：

   1
    \
     2
    / \
   3   4
        \
         5
          \
           6
步骤 4：移动 curr
  • curr 向右移动到 2（原左子树的根节点）。
  • 重复上述过程：
    1. predecessor 从 3 开始，向右走到 3（因为 3.right 为 null）。
    2. 将 2 的右子树（4）挂到 3 的右指针：
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      1
       \
        2
       / 
      3   
       \
        4
         \
          5
           \
            6
    3. 将左子树（3）移到 2 的右指针，左指针置空：
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      1
       \
        2
         \
          3
           \
            4
             \
              5
               \
                6

代码逐行解析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var flatten = function(root) {
    let curr = root;
    while (curr) {
        if (curr.left) {
            // 1. 找到左子树的最右节点
            let predecessor = curr.left;
            while (predecessor.right) {
                predecessor = predecessor.right;
            }
            
            // 2. 将右子树挂到最右节点
            predecessor.right = curr.right;
            
            // 3. 将左子树移到右子树位置
            curr.right = curr.left;
            curr.left = null;
        }
        // 4. 移动到下一个节点
        curr = curr.right;
    }
};
代码行 作用
let curr = root 初始化当前节点为根节点
if (curr.left) 检查是否存在左子树
predecessor = curr.left 从左子树的根节点开始
while (predecessor.right) 找到左子树的最右节点
predecessor.right = curr.right 将右子树接到最右节点
curr.right = curr.left 左子树变为右子树
curr.left = null 左指针置空
curr = curr.right 移动到处理后的下一个节点

为什么能保证正确性？

  1. 先序遍历顺序：
    • 每次将左子树移到右侧，保证了 根 -> 左 -> 右 的顺序。
  2. 指针修改的安全性：
    • predecessor 的右指针原本是 null，临时存储原右子树不会丢失信息。
  3. 终止条件：
    • 当 curr 移动到叶子节点时（curr.right === null），循环结束。

复杂度分析

操作 时间复杂度 空间复杂度
遍历所有节点 O(n) -
查找 predecessor 每个节点最多被访问两次 -
总计 O(n) O(1)

总结

  • 适用场景：需要原地修改且空间限制严格时。
  • 关键技巧：利用空闲指针（叶子节点的右指针）临时存储右子树。
  • 对比递归：避免了递归栈空间，适合深层树结构。

方法对比

方法 时间复杂度 空间复杂度 特点
递归（非原地） O(n) O(n) 简单直观，但需要额外空间
递归（原地） O(n) O(h) 原地修改，递归栈可能溢出
迭代（Morris） O(n) O(1) 最优解，无递归栈问题

关键点总结

  1. 先序遍历顺序：展开后的链表必须与先序遍历顺序一致。
  2. 原地修改：直接修改指针，不新建数据结构。
  3. Morris遍历：通过修改指针实现 O(1) 空间复杂度。

最终推荐代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 方法三：迭代（Morris遍历）
var flatten = function(root) {
    let curr = root;
    while (curr) {
        if (curr.left) {
            let predecessor = curr.left;
            while (predecessor.right) {
                predecessor = predecessor.right;
            }
            predecessor.right = curr.right;
            curr.right = curr.left;
            curr.left = null;
        }
        curr = curr.right;
    }
};