汀的知识碎片

04 二叉树指针操作：展开链表与填充右侧指针

8 min read

二叉树指针操作：展开链表与填充右侧指针

摘要

从遍历和判定题进入“原地改树”之后，二叉树专题的难度会上一个台阶。LeetCode 114 要求把树展开为先序顺序的链表，LeetCode 116 与 117 则要求把每一层的横向相邻节点用 next 指针串起来。它们共同训练的能力是：当你不再只是读一棵树，而要修改树的指针结构时，如何保证局部调整不会破坏尚未处理的部分。本文会分别从 DFS 重连和 BFS 分层连接两条思路讲清楚这类题。

第 1 章 LeetCode 114：Flatten Binary Tree to Linked List

1.1 题目本质

要求把一棵二叉树原地展开为链表，最终形式是：

  • 每个节点的 left 都为 null
  • right 指针按照前序遍历顺序串起整棵树

这意味着目标结构不是随意的链表，而是前序序列的线性化结果。

1.2 为什么前序信息决定最终顺序

因为前序遍历是“根、左、右”，而展开后的链表也要求根节点后面先接左子树展开结果，再接右子树展开结果。因此可以把问题理解成：

  1. 先把左子树展开
  2. 再把右子树展开
  3. 把左链表插入到根节点和右链表之间

1.3 后序重连写法

public void flatten(TreeNode root) {
    flattenTree(root);
}
 
private TreeNode flattenTree(TreeNode node) {
    if (node == null) {
        return null;
    }
 
    TreeNode leftTail = flattenTree(node.left);
    TreeNode rightTail = flattenTree(node.right);
 
    if (node.left != null) {
        TreeNode originalRight = node.right;
        node.right = node.left;
        node.left = null;
        leftTail.right = originalRight;
    }
 
    if (rightTail != null) {
        return rightTail;
    }
    if (leftTail != null) {
        return leftTail;
    }
    return node;
}

这里函数返回的是“当前子树展开后链表的尾节点”。为什么需要尾节点？因为父节点要把自己的左链表尾巴接到原来的右链表头上。

1.4 为什么这题虽然是前序目标，却常用后序解

最终结果顺序确实是前序，但实现时你需要先知道左右子树各自展开后的边界，才能做安全拼接。因此从控制流上看，它是典型后序：先处理左右，再处理当前节点。

第 2 章 LeetCode 116：完美二叉树中的 Next 指针连接

2.1 完美二叉树给了什么额外条件

LeetCode 116 中树是完美二叉树，也就是：

  • 每个非叶子节点都有两个孩子
  • 所有叶子都在同一层

这个条件意味着一个节点的 left 和 right 一定存在，而且同层结构非常规则。

2.2 BFS 是最直白的解法

public Node connect(Node root) {
    if (root == null) {
        return null;
    }
 
    Queue<Node> queue = new LinkedList<>();
    queue.offer(root);
 
    while (!queue.isEmpty()) {
        int size = queue.size();
        Node prev = null;
        for (int i = 0; i < size; i++) {
            Node node = queue.poll();
            if (prev != null) {
                prev.next = node;
            }
            prev = node;
 
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
    }
    return root;
}

队列按层推进，prev 负责把当前层相邻节点串起来。这和普通层序遍历的差别只是在每层多维护了一个“上一个节点”。

2.3 利用完美二叉树性质的 O(1) 空间写法

因为每层都是完整的，我们可以利用上一层已经连好的 next 指针，去串下一层：

public Node connect(Node root) {
    if (root == null) {
        return null;
    }
 
    Node leftmost = root;
    while (leftmost.left != null) {
        Node head = leftmost;
        while (head != null) {
            head.left.next = head.right;
            if (head.next != null) {
                head.right.next = head.next.left;
            }
            head = head.next;
        }
        leftmost = leftmost.left;
    }
    return root;
}

这个写法很漂亮，但它强依赖完美二叉树条件。只要结构不完整，就不能直接套用。

第 3 章 LeetCode 117：一般二叉树中的 Next 指针连接

3.1 为什么 116 的 O(1) 技巧不能直接照搬

在普通二叉树里：

  • 某节点可能没有左孩子
  • 某节点可能没有右孩子
  • head.next.left 也未必存在

因此不能再依赖“孩子位置固定”的结构性质。

3.2 最稳的 BFS 写法

public Node connect(Node root) {
    if (root == null) {
        return null;
    }
 
    Queue<Node> queue = new LinkedList<>();
    queue.offer(root);
 
    while (!queue.isEmpty()) {
        int size = queue.size();
        Node prev = null;
        for (int i = 0; i < size; i++) {
            Node node = queue.poll();
            if (prev != null) {
                prev.next = node;
            }
            prev = node;
 
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
    }
    return root;
}

本质和 116 的 BFS 版本完全一致，因为层序边界不依赖树是否完美。

3.3 进阶：用已建立的 next 指针串下一层

如果追求常数空间，也能做，但实现要更细：

  • 用 current 沿当前层的 next 链横向走
  • 用 dummy 和 tail 构造下一层链表
  • 当前层走完后，跳到 dummy.next

这个技巧的核心思想和链表构造很像：用哑节点统一处理下一层第一个元素的接入。

第 4 章 这三道题共同训练了什么

题目本质关键状态
LC114原地修改树结构子树展开后的尾节点
LC116同层节点连接每层的前一个节点，或上一层 next 链
LC117非规则层连接当前层横向遍历 + 下一层尾指针

它们的共同点是：你不能只考虑“当前节点对不对”，还要考虑“改完之后，剩余未处理结构是否还可达”。这就是指针题比普通遍历题更难的原因。

指针重连最怕先把入口丢掉

在任何原地改链结构的题里，只要你需要保留旧的 right、旧的 next、旧的尾节点，就一定要先存下来，再改指针。顺序错了，结构就断了。

下一篇预告

05 二叉树重建：前序+中序、后序+中序的构造逻辑 会进入二叉树构造题。你会看到，树的重建不是背公式，而是精确切分遍历数组区间的过程。

Backlinks