LeetCode 114 二叉树展开为链表Flatten Binary Tree to Linked List 题解全解析【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode导读本文围绕 leetcode 仓库「每日一题」系列中的 daily/2019-06-14.md 展开深入剖析 LeetCode 114「Flatten Binary Tree to Linked List二叉树展开为链表」这道经典树题。文章完整继承并扩充了原文档给出的先序遍历重建法、原地递归法和栈式非递归法三种解法并结合仓库中的 JS 参考实现 与树/遍历专题文档讲解每类方法的思路、代码与复杂度。读完本文你将掌握如何把一棵二叉树原地展开为右子树方向的单链表并能独立分析递归与栈两种 DFS 实现的异同。原文档出自 daily/README.md 记录的「每日一题」活动2019-06-14 当日题目为 114.flatten-binary-tree-to-linked-listtag 为tree、Recursion。题目描述与关键约束原文档给出的题目如下Given a binary tree, flatten it to a linked list in-place.例如给定如下二叉树1 / \ 2 5 / \ \ 3 4 6展开后应得到1 \ 2 \ 3 \ 4 \ 5 \ 6这题有两个容易忽略的约束决定了我们的写法原地修改in-place函数不返回新树而是直接修改传入的root节点本身。文档中的 JS 函数签名也明确注明Do not return anything, modify root in-place instead.。展开形态所有节点都挂在right指针上left全部置空整棵树退化成为一条单链表。注意展开后节点的相对顺序恰好是**先序遍历根-左-右**的顺序这正是方法一的切入点。方法一先序遍历 重建JavaScriptO(n) 时间 / O(n) 空间核心思路原文档敏锐地指出如果仔细观察输入输出的话会发现其实输出其实就是输入的先序遍历结果而已。因此最简单的做法分两步对原树做一次先序遍历按遍历顺序收集所有节点把这些节点按顺序串成一条只有右指针的链每个节点的left置空right指向下一个节点。参考代码仓库原版原文档给出的完整实现如下/* * lc appleetcode id114 langjavascript * * [114] Flatten Binary Tree to Linked List */ /** * Definition for a binary tree node. * function TreeNode(val) { * this.val val; * this.left this.right null; * } */ function preorderTraversal(root) { if (!root) return []; return [root] .concat(preorderTraversal(root.left)) .concat(preorderTraversal(root.right)); } /** * param {TreeNode} root * return {void} Do not return anything, modify root in-place instead. */ var flatten function(root) { if (root null) return root; const res preorderTraversal(root); let curPos 0; let curNode res[0]; while(curNode res[curPos]) { curNode.left null; curNode.right res[curPos]; } };这段代码与仓库中的 daily/answers/114.flatten-binary-tree-to-linked-list.js 基本一致可以作为仓库每日一题答案模块的落地实现来参考。代码细节解读preorderTraversal采用递归方式实现先序遍历根节点在前递归拼接左子树结果与右子树结果。concat会把子数组展开因此res是TreeNode节点而非数组组成的先序序列。flatten中curPos从 0 开始while (curNode res[curPos])的赋值表达式在res越界返回undefined时自然终止无需显式判断长度。每个节点依次把left置空、right指向res[curPos]最后一个节点的right指向undefined与初始结构一致。复杂度Time complexity : O(n)—— 一次先序遍历 一次线性重连n 为节点数。Space complexity : O(n)—— 递归栈深度在最坏情况下为 O(n)退化为链表形态的树且额外使用了数组存储全部节点。该方法的代价在于它不是严格意义上的原地先序遍历数组占用了额外空间。方法二通过后序遍历式的递归把空间降到了只有递归栈是对方法一的优化。方法二递归原地展开CO(n) 时间 / O(h) 空间算法描述原文档原文档给出的递归子问题思想如下递归遍历把一棵树左子树变成单链表 a递归遍历把一棵树右子树变成单链表 b用链表 a 的最后一个元素拼接链表 b递归子问题。这实际上是一种后序遍历式的处理顺序先处理好左右子树再处理当前根节点。原因在于展开右子树链时我们需要知道左子树链的末尾节点而这个信息必须等左子树完全展开后才能确定因此先子后父是必然的。递归参考代码Cvoid flatten(TreeNode* root) { if (root NULL) return ; flatten(root-left); flatten(root-right); //递归子问题 TreeNode *tmp root-right; root-right root-left; root-left NULL; while (root-right) { root root-right; }; root-right tmp; }逐步推演以题目示例的树为例根 1左子树 2→3→4右子树 5→6先flatten(root-left)把以 2 为根的子树展成链2→3→4再flatten(root-right)把以 5 为根的子树展成链5→6回到根节点 1先用tmp暂存原右孩子 5再把root-right指向已展开的左链2→3→4root-left置空while (root-right)沿链走到末尾节点 4把4-right接上tmp即5→6。最终得到1→2→3→4→5→6与题目要求完全一致。代码中的tmp指针承担了先保存右子树、再拼接的关键职责而末尾节点的查找正是原文档强调的递归子问题。复杂度时间 O(n)每个节点恰好被访问一次加上沿左链找末尾节点的开销均摊仍为 O(n)。空间 O(h)h 为树高。递归栈深度等于树高最坏情况斜树下为 O(n)优于方法一的额外数组。方法三栈式非递归先序遍历CO(n) 时间 / O(n) 空间算法思路原文档给出的非递归版本核心思想是用栈模拟先序遍历在出栈的同时直接完成指针重连省去递归调用。void flatten(TreeNode* root) { if (root NULL) { return ; } stackTreeNode* result; result.push(root); while (!result.empty()){ TreeNode* curresult.top(); result.pop(); if (cur-right) { result.push(cur-right);//先顺非递归遍历 } if (cur-left) { result.push(cur-left);//先顺非递归遍历 } //递归子问题 if (!result.empty()) { cur-rightresult.top(); } cur-leftNULL; } }关键点说明先序顺序的保证由于栈是后进先出必须先压右孩子、再压左孩子这样下一次出栈的才是左孩子从而维持根-左-右的遍历顺序代码注释中的先顺非递归遍历即此意。遍历与重连合一每个节点出栈时直接把cur-right指向栈顶即下一个要访问的节点同时cur-left NULL。这样栈的遍历顺序天然就是最终链表的顺序不需要额外的数组。该非递归做法与仓库 thinkings/binary-tree-traversal.md 中总结的前序遍历模板一致——该专题文档明确写道先将根结点入栈出栈一个元素将右节点和左节点依次入栈重复上述步骤。可以对照阅读二者互为印证。三种方法对比与总结方法遍历顺序是否原地时间空间语言方法一先序遍历 重建先序显式收集否需数组O(n)O(n)JavaScript方法二递归原地展开后序先子后父是O(n)O(h)C方法三栈式非递归先序边遍历边重连是O(n)O(n)C选择建议面试中最推荐方法二写法直观、空间最优且先处理子树、再处理当前节点的思维在树类问题中非常通用若想避免递归深度问题可用方法三但需牢记先右后左的入栈顺序方法一最适合快速理解题目本质展开结果就是先序遍历序列。相关仓库资源延伸阅读每日一题活动说明与历史题目汇总见 daily/README.md其中 2019-06-14 条目 记录了本题的 tag 与时间信息仓库提供了本题的独立 JS 答案文件 daily/answers/114.flatten-binary-tree-to-linked-list.js是方法一代码的可运行版本树专题总纲 thinkings/tree.md 系统讲解了递归思维、先序/后序遍历的时机选择以及遍历是为了更好地做处理的核心观点遍历专题 thinkings/binary-tree-traversal.md 给出了前序、中序、后序的递归与栈实现模板本题的三种解法都可以在其中找到对应原型相关遍历题目可延伸练习144.binary-tree-preorder-traversal.md、94.binary-tree-inorder-traversal.md、145.binary-tree-postorder-traversal.md。小结Flatten Binary Tree to Linked List 是一道典型的遍历 指针重连树题它表面问的是链表化本质考的是对先序遍历的理解与原地修改指针的能力。掌握本文三种解法先序重建、递归原地、栈式非递归后你可以清晰地看到同一种遍历思想在空间换时间与原地优化之间的不同落法也能为后续处理 Morris 遍历、线索二叉树等进阶话题打下基础。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考