企业官网建设流程全解析

题目描述：

给你二叉树的根结点root，请你将它展开为一个单链表：

• 展开后的单链表应该同样使用TreeNode，其中right子指针指向链表中下一个结点，而左子指针始终为null。
• 展开后的单链表应该与二叉树 先序遍历 顺序相同。

示例 1：

输入：root = [1,2,5,3,4,null,6]输出：[1,null,2,null,3,null,4,null,5,null,6]

示例 2：

输入：root = []输出：[]

示例 3：

输入：root = [0]输出：[0]

解题思路：

方法一：递归（后序遍历）

核心思路：

对于任意节点root：

1. 递归展开左子树，得到左子树链表

2. 递归展开右子树，得到右子树链表

3. 拼接：

   • 把左子树链表接到root->right

   • 把右子树链表接到左子树链表的末尾

   • root->left = nullptr

具体过程示例：

1 / \ 2 5 / \ \ 3 4 6 第1步: 递归展开左子树(2) 2 \ 3 \ 4 第2步: 递归展开右子树(5) 5 \ 6 第3步: 拼接 1 \ 2 \ 3 \ 4 \ 5 \ 6 ✅

代码实现：

写法1：后序遍历（推荐）

class Solution { public: void flatten(TreeNode* root) { if (root == nullptr) return; // 先递归展开左右子树 flatten(root->left); flatten(root->right); // 保存右子树 TreeNode* right = root->right; // 把左子树接到右边 root->right = root->left; root->left = nullptr; // 找到当前右子树的末尾，接上原来的右子树 TreeNode* curr = root; while (curr->right != nullptr) { curr = curr->right; } curr->right = right; } };

写法2：前序遍历（用栈）

class Solution { public: void flatten(TreeNode* root) { if (root == nullptr) return; stack<TreeNode*> stk; stk.push(root); TreeNode* prev = nullptr; while (!stk.empty()) { TreeNode* curr = stk.top(); stk.pop(); if (prev != nullptr) { prev->right = curr; prev->left = nullptr; } // 先压右，再压左（保证左先出栈） if (curr->right) stk.push(curr->right); if (curr->left) stk.push(curr->left); prev = curr; } } };

复杂度分析：

写法1（后序递归）

问题：找右子树末尾的while循环导致 O(n²)。

写法2（前序栈）

关键细节：

1. 为什么后序递归（全局 prev）能 O(n)？

• 遍历顺序：右 → 左 → 根

• 每次处理当前节点时，prev已经指向了"前序遍历中的下一个节点"

• 直接把root->right = prev即可，不需要找末尾

2. 图解后序递归（全局 prev）

1 / \ 2 5 / \ \ 3 4 6 遍历顺序: 6 → 5 → 4 → 3 → 2 → 1 处理6: prev=null, 6->right=null, prev=6 处理5: prev=6, 5->right=6, prev=5 处理4: prev=5, 4->right=5, prev=4 处理3: prev=4, 3->right=4, prev=3 处理2: prev=3, 2->right=3, prev=2 处理1: prev=2, 1->right=2, prev=1 结果: 1 → 2 → 3 → 4 → 5 → 6 ✅

3. 为什么前序栈要"先压右，再压左"？

因为栈是后进先出：

• 先压右，右在栈底

• 再压左，左在栈顶

• 弹出时先弹出左，符合前序顺序

方法二：找左子树的最右节点(原地算法)

核心思路：

对于每个节点root：

1. 如果root->left == nullptr，直接跳到root->right

2. 如果root->left != nullptr：

   • 找到左子树的最右节点（前序前驱）

   • 把root->right接到这个最右节点的右边

   • 把root->left移到root->right

   • root->left = nullptr

   • 继续处理新的root->right

具体过程示例：

1 / \ 2 5 / \ \ 3 4 6 处理节点1: 左子树是2，找左子树的最右节点 → 4 把 1->right (5) 接到 4->right 把 1->left (2) 移到 1->right 1->left = nullptr 1 \ 2 / \ 3 4 \ 5 \ 6 处理节点2: 左子树是3，找左子树的最右节点 → 3 把 2->right (4) 接到 3->right 把 2->left (3) 移到 2->right 2->left = nullptr 1 \ 2 \ 3 \ 4 \ 5 \ 6 继续处理3、4、5、6，最终得到: 1 → 2 → 3 → 4 → 5 → 6 ✅

代码实现：

class Solution { public: void flatten(TreeNode* root) { TreeNode* curr = root; while (curr != nullptr) { if (curr->left != nullptr) { // 找到左子树的最右节点（前序前驱） TreeNode* prev = curr->left; while (prev->right != nullptr) { prev = prev->right; } // 把当前节点的右子树接到前驱的右边 prev->right = curr->right; // 把左子树移到右边 curr->right = curr->left; curr->left = nullptr; } // 继续处理下一个节点 curr = curr->right; } } };

复杂度分析：

为什么是 O(n)？

• 外层while遍历每个节点一次

• 内层while找最右节点，但每条边最多被走两次

• 总操作次数 O(n)

关键细节：

1. 为什么找"左子树的最右节点"？

因为前序遍历的顺序是：根 → 左子树 → 右子树

• 左子树的最后一个节点（最右节点）就是右子树的前驱

• 把右子树接到它后面，正好符合前序顺序

2. 为什么curr = curr->right不会死循环？

每次处理完当前节点后：

• curr->right指向了左子树的根

• curr->left被置空

• 所以curr = curr->right会走到左子树的根，继续处理

• 最终会走到nullptr，循环结束

3. 为什么时间复杂度是 O(n) 而不是 O(n²)？

虽然内层while看起来可能很耗时，但：

• 每条边最多被走两次（一次找最右节点，一次遍历）

• 总操作次数与节点数成正比

• 所以是 O(n)

三种方法对比：

总结：