【LeetCode 热题 100】114. 二叉树展开为链表——（解法一）后序遍历+头插法

2026/8/15 13:33:32 拓冰建站浏览量

Problem: 114. 二叉树展开为链表
给你二叉树的根结点 root ，请你将它展开为一个单链表：
展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树先序遍历顺序相同。

文章目录

整体思路
完整代码
时空复杂度
- 时间复杂度：O(N)
- 空间复杂度：O(H)

整体思路

这段代码旨在解决一个经典的二叉树问题：二叉树展开为链表 (Flatten Binary Tree to Linked List)。问题要求将一个二叉树原地转换成一个“链表”结构。这个“链表”实际上是利用树节点的 right 指针串联起来的，所有节点的 left 指针都应设为 null。展开后的顺序应与二叉树的前序遍历顺序一致。

该实现采用了一种非常巧妙的 “后序遍历的变种” 结合 头插法 的思想。它通过递归，从树的底部向上构建这个链表。

遍历顺序：
- flatten(root.right);
- flatten(root.left);
- // 处理 root 节点
- 这种 “右-左-根” 的遍历顺序是算法的核心。它保证了在处理当前 root 节点时，它的右子树和左子树都已经各自被“拉平”成了链表。
链表构建逻辑：
- 算法使用一个全局（或类成员）变量 head，它扮演着已处理好的链表的头节点的角色。
- 当递归回溯到处理 root 节点时，执行以下操作：
  a. root.left = null;: 将当前节点的左指针置空，满足题目要求。
  b. root.right = head;: 将当前节点的右指针指向 head，即指向已经处理好的、位于其右侧的链表。这相当于将 root 节点插入到链表的头部。
  c. head = root;: 更新 head，让它指向新的链表头，也就是刚刚处理完的 root 节点。
算法流程举例：
- 考虑一个简单的树 [1, 2, 3]。
- flatten(1) 调用 flatten(3) (右子树)。
- flatten(3) 没有子节点，处理 3：3.left=null, 3.right=head(null), head=3。此时链表是 3。
- 回溯到 flatten(1)，调用 flatten(2) (左子树)。
- flatten(2) 没有子节点，处理 2：2.left=null, 2.right=head(3), head=2。此时链表是 2 -> 3。
- 回溯到 flatten(1)，处理 1：1.left=null, 1.right=head(2), head=1。此时链表是 1 -> 2 -> 3。
- 整个过程结束，树被成功展开。

这个算法的精妙之处在于，通过逆向的遍历（先处理右子树），它能很自然地将当前节点“链接”到已经构建好的链表的前端，而不需要在递归函数之间传递链表的尾部节点。

完整代码

class Solution {// head: 成员变量，用于在递归调用中跟踪已展开链表的头节点。private TreeNode head;/*** 将给定的二叉树原地展开为链表。* 展开后的顺序与前序遍历一致。* @param root 二叉树的根节点*/public void flatten(TreeNode root) {// 基线条件：如果节点为空，则直接返回。if (root == null) {return;}// 关键的遍历顺序：右、左、根 (后序遍历的变种)// 1. 递归地将右子树展开为链表。//    执行完毕后，head 会指向右子树展开后链表的头部。flatten(root.right);// 2. 递归地将左子树展开为链表。//    执行完毕后，head 会指向左子树展开后链表的头部，//    并且这个链表已经正确地连接到了原右子树链表的前面。flatten(root.left);// 3. 处理当前根节点 root// a. 将 root 的左指针置为 null，满足题目要求。root.left = null;// b. 将 root 的右指针指向已经处理好的链表的头部 (head)。//    这相当于将 root 节点作为新的头节点插入到链表前端。root.right = head;// c. 更新 head，使其指向新的链表头，即当前的 root 节点。head = root;}
}

时空复杂度

时间复杂度：O(N)

节点访问：该算法通过递归遍历了树中的每一个节点。每个节点被访问和处理一次。
操作：在每个节点上，执行的都是常数时间的指针操作。
综合分析：
- 如果树中有 N 个节点，flatten 函数会被调用 N 次。
- 因此，总的时间复杂度与节点数成正比，即 O(N)。

空间复杂度：O(H)

主要存储开销：算法是原地修改，没有创建新的数据结构来存储节点。主要的额外空间开销来自于 递归调用栈。
空间大小：递归调用的深度取决于树的高度 H。
- 在最好的情况下（一个完全二叉树），树的高度 H 约为 log N，空间复杂度为 O(log N)。
- 在最坏的情况下（一个极度倾斜的链状树），树的高度 H 等于 N，此时递归栈的深度也为 N，空间复杂度为 O(N)。
成员变量：head 变量只占用 O(1) 的空间。

综合分析：
算法的辅助空间复杂度主要由递归栈的深度决定，即树的高度 H。因此，空间复杂度为 O(H)。在最坏情况下，H 可能为 N，所以最坏空间复杂度也可以表述为 O(N)。

【LeetCode 热题 100】114. 二叉树展开为链表——（解法二）分治

参考灵神

建站实战干货