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

题目描述给你二叉树的根结点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递归展开左子树得到左子树链表递归展开右子树得到右子树链表拼接把左子树链表接到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; stackTreeNode* 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后序递归维度复杂度说明时间复杂度O(n²)每次找右子树末尾需要 O(n)空间复杂度O(h)递归栈深度问题找右子树末尾的while循环导致 O(n²)。写法2前序栈维度复杂度说明时间复杂度O(n)每个节点入栈出栈各一次空间复杂度O(n)栈最多存储 n 个节点关键细节1. 为什么后序递归全局 prev能 O(n)遍历顺序右 → 左 → 根每次处理当前节点时prev已经指向了前序遍历中的下一个节点直接把root-right prev即可不需要找末尾2. 图解后序递归全局 prev1 / \ 2 5 / \ \ 3 4 6 遍历顺序: 6 → 5 → 4 → 3 → 2 → 1 处理6: prevnull, 6-rightnull, prev6 处理5: prev6, 5-right6, prev5 处理4: prev5, 4-right5, prev4 处理3: prev4, 3-right4, prev3 处理2: prev3, 2-right3, prev2 处理1: prev2, 1-right2, prev1 结果: 1 → 2 → 3 → 4 → 5 → 6 ✅3. 为什么前序栈要先压右再压左因为栈是后进先出先压右右在栈底再压左左在栈顶弹出时先弹出左符合前序顺序方法二找左子树的最右节点(原地算法)核心思路对于每个节点root如果root-left nullptr直接跳到root-right如果root-left ! nullptr找到左子树的最右节点前序前驱把root-right接到这个最右节点的右边把root-left移到root-rightroot-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)每个节点最多被访问两次空间复杂度O(1)只用了几个指针为什么是 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)三种方法对比方法时间复杂度空间复杂度是否原地推荐度后序递归全局 prevO(n)O(h)❌ 递归栈⭐⭐⭐⭐⭐前序栈O(n)O(n)❌ 栈⭐⭐⭐⭐原地算法O(n)O(1)✅原地⭐⭐⭐⭐⭐总结要点说明核心思想找左子树最右节点把右子树接过去关键操作prev-right curr-right; curr-right curr-left; curr-left nullptr时间复杂度O(n)空间复杂度O(1)