【二叉树】LC 114.二叉树展开为链表

文章目录

• 前言
• 一、题目
• • 1、原题链接
  • 2、题目描述
• 二、个人思路整理
• • 1、思路分析
  • • 思路1：寻找前驱节点
    • 思路2：倒序递归
    • 思路3：显式栈模拟前序遍历
  • 2、解题代码
  • • 思路1：寻找前驱节点
    • 思路2：倒序递归
    • 思路3：显式栈模拟前序遍历
• 三、知识风暴

前言

本专栏文章为《LeetCode 热题 100》的刷题题解，相关内容如有侵权，立即删除。

一、题目

1、原题链接

114.二叉树展开为链表

2、题目描述

二、个人思路整理

1、思路分析

思路1：寻找前驱节点

核心思路： 在前序遍历中，根节点的右子树一定紧接在左子树的最右侧节点（即左子树中前序遍历的最后一个节点）之后。

思路2：倒序递归

核心思路： 常规前序遍历是 根 -> 左 -> 右，如果直接正序修改指针会破坏原有的右子树连接。但若采用逆先序遍历（右 -> 左 -> 根），后访问到的节点恰好是链表的前驱，可以直接维护一个全局/类成员指针 pre 记录已处理好的链表头节点。

思路3：显式栈模拟前序遍历

核心思路： 用栈进行前序遍历，每次出栈一个节点作为当前节点，将其右孩子和左孩子依次入栈（保证左孩子先出栈）。维护一个 pre 指针指向前一个访问的节点，在遍历过程中建立单链表连接。

2、解题代码

思路1：寻找前驱节点

/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void flatten(TreeNode* root) {
TreeNode* cur = root;
while (cur != nullptr) {
if (cur->left != nullptr) {
// 1. 找到左子树的最右节点
TreeNode* predecessor = cur->left;
while (predecessor->right != nullptr) {
predecessor = predecessor->right;
}
// 2. 将原右子树接到最右节点的右侧
predecessor->right = cur->right;
// 3. 将左子树移到右子树，并置空左指针
cur->right = cur->left;
cur->left = nullptr;
}
// 4. 继续处理下一个节点
cur = cur->right;
}
}
};

复杂度分析

• 时间复杂度： $O(n)$
• 空间复杂度： $O(1)$

思路2：倒序递归

/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
private:
TreeNode* pre = nullptr;
public:
void flatten(TreeNode* root) {
if (root == nullptr) {
return;
}

// 先处理右子树，再处理左子树
flatten(root->right);
flatten(root->left);

// 修改当前节点的指向
root->right = pre;
root->left = nullptr;
pre = root;
}
};

复杂度分析

• 时间复杂度： $O(n)$
• 空间复杂度： $O(h)$

思路3：显式栈模拟前序遍历

/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void flatten(TreeNode* root) {
// 空树直接返回
if (root == nullptr) {
return;
}

// 使用显式栈模拟前序遍历
stack<TreeNode*> stk;
stk.push(root);
TreeNode* pre = nullptr; // 记录前序遍历的上一个节点

while (!stk.empty()) {
TreeNode* cur = stk.top();
stk.pop();

// 如果存在前驱节点，将前驱的右指针直系那个当前节点，左指针置空
if (pre != nullptr) {
pre->left = nullptr;
pre->right = cur;
}

// 栈是后进先出，为了保证 先左后右 的出栈顺序，先压入右子节点，再压入左子节点
if (cur->right) {
stk.push(cur->right);
}
if (cur->left) {
stk.push(cur->left);
}

// 更新 pre 为当前节点，供下一轮连接使用
pre = cur;
}
}
};

复杂度分析

• 时间复杂度： $O(n)$
• 空间复杂度： $O(n)$

三、知识风暴

前序遍历（Preorder Traversal） 是本题的核心：二叉树展开为链表的过程，本质上就是按照前序遍历的顺序 根 -> 左 -> 右 重新组织节点，使每个节点的 right 指针指向前序遍历中的下一个节点，left 指针全部置空。最终得到的链表顺序恰好就是原二叉树的前序遍历序列。

算法核心思想：

• 前序遍历顺序：前序遍历的顺序是 根 -> 左子树 -> 右子树。展开后的链表顺序必须严格遵循这一顺序，因此无论采用哪种实现方式，核心都是保证最终 right 指针的连接顺序为前序遍历序列。
• 原地修改：题目要求原地展开（in-place），即不能新建链表节点，只能在原树上修改 left 和 right 指针。这要求我们在修改指针时不能丢失尚未处理的子树引用。
• 指针置空：展开过程中，每个节点的 left 指针最终都必须置为 nullptr，只保留 right 指针形成单链表。

常见对比：递归 vs 迭代（显式栈）

• 递归（倒序递归）：采用逆先序遍历（右 -> 左 -> 根），利用递归调用栈天然保存了回溯路径，代码简洁；但空间复杂度为 $O(h)$
• 迭代（显式栈）：用栈模拟前序遍历，每次出栈一个节点并建立连接，空间复杂度同样为 $O(n)$
• 迭代（寻找前驱节点）：这是本题最优解，空间复杂度为 $O(1)$

Morris 遍历思想：

• 核心思想：Morris 遍历利用叶子节点的空闲指针（right 指针）临时记录回溯路径，从而在不使用栈和递归的情况下实现 $O(1)$
• 与本题的联系：思路1（寻找前驱节点）本质上借鉴了 Morris 遍历的思想——通过找到左子树的最右节点（前驱节点）来临时保存右子树的位置，从而在不丢失信息的前提下完成指针重排。
• 区别：Morris 遍历通常用于中序遍历，且遍历结束后会恢复树的原始结构；而本题的展开过程是永久性地修改指针结构，最终得到链表。

使用要点：

• 前驱节点的定位：在思路1中，predecessor 是 cur->left 子树中最右侧的节点，即左子树前序遍历的最后一个节点。找到它之后，把 cur->right 接到 predecessor->right，这样右子树的信息就不会丢失。
• 左子树右移：将 cur->left 移到 cur->right 后，必须立即将 cur->left 置空，否则会残留左指针，破坏链表结构。
• 循环推进：处理完当前节点后，cur 移向 cur->right（即原来的左子树根节点），继续处理，直到 cur 为空。
• 空树处理：若根节点为空，直接返回，作为边界条件的兜底。

算法变体与扩展：

• 二叉树的前序遍历（LeetCode 144）：本题展开后的链表顺序就是前序遍历序列，理解前序遍历是解题的基础。
• 二叉树的中序遍历（LeetCode 94）：Morris 遍历的经典应用场景，与本题的前驱节点思想同源。
• 填充每个节点的下一个右侧节点指针（LeetCode 116）：同样是利用指针在树上建立链表结构，与本题的指针重排思路相似。
• 将有序数组转换为二叉搜索树（LeetCode 108）：与本题相反，是从线性结构重建二叉树，可对比理解树与链表的相互转换。

相关 LeetCode 例题：

• 144. 二叉树的前序遍历（递归 / 迭代 / Morris 三种实现）
• 94. 二叉树的中序遍历（Morris 遍历经典应用）
• 116. 填充每个节点的下一个右侧节点指针（指针重排建立链表）
• 114. 二叉树展开为链表（本题，前序遍历 + 原地指针修改）