二叉树展开为链表：从先序遍历到原地指针重排

一、题目描述LeetCode 114「二叉树展开为链表」要求我们将一棵二叉树展开成一个单链表。题目给定二叉树的根节点root要求将其原地展开为一个链表展开后的链表仍然使用TreeNode结构。展开后的链表需要满足以下条件链表顺序与二叉树的先序遍历顺序一致每个节点的right指针指向链表中的下一个节点每个节点的left指针都必须为nullptr尽量使用原地算法完成进阶要求是O(1)额外空间。例如输入root [1,2,5,3,4,null,6]原始二叉树结构如下1 / \ 2 5 / \ \ 3 4 6它的先序遍历结果是1 - 2 - 3 - 4 - 5 - 6所以展开后的结构应该是1 \ 2 \ 3 \ 4 \ 5 \ 6所有节点的left指针都应该为空。二、问题本质这道题的本质是将二叉树按照先序遍历顺序原地改造成一条只使用right指针连接的链表。先序遍历的顺序是根节点 - 左子树 - 右子树所以对于任意一个节点root展开后的顺序应该是root - root.left 展开后的链表 - root.right 展开后的链表难点在于原来的右子树不能丢失同时左子树需要移动到右边。因此核心操作是将左子树接到右指针上 再把原来的右子树接到左子树展开链表的末尾 最后将 left 置空三、最直观思路先序遍历保存节点最容易想到的做法是先对二叉树做一次先序遍历将遍历到的节点依次存入数组再根据数组顺序重新连接节点。这种方法非常直观。代码实现#include vector using namespace std; 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) { vectorTreeNode* nodes; preorder(root, nodes); for (int i 1; i nodes.size(); i) { TreeNode* prev nodes[i - 1]; TreeNode* curr nodes[i]; prev-left nullptr; prev-right curr; } } private: void preorder(TreeNode* root, vectorTreeNode* nodes) { if (root nullptr) { return; } nodes.push_back(root); preorder(root-left, nodes); preorder(root-right, nodes); } };方法分析这种方法逻辑清晰适合初学者理解。但是它使用了一个额外数组nodes保存所有节点因此空间复杂度是O(n)不满足题目进阶要求的O(1)额外空间。四、递归优化反向先序遍历除了正向先序遍历还可以从反方向思考。先序遍历是根 - 左 - 右如果我们反过来处理就是右 - 左 - 根我们可以维护一个指针prev表示当前节点展开后应该连接的下一个节点。处理顺序如下先展开右子树再展开左子树最后处理当前节点当前节点的right指向prev当前节点的left置空更新prev 当前节点。这样可以从后往前构造链表。代码实现class Solution { private: TreeNode* prev nullptr; public: void flatten(TreeNode* root) { if (root nullptr) { return; } flatten(root-right); flatten(root-left); root-right prev; root-left nullptr; prev root; } };执行过程理解对于这棵树1 / \ 2 5 / \ \ 3 4 6反向处理顺序为6 - 5 - 4 - 3 - 2 - 1每处理一个节点就把它接到当前已经构造好的链表头部。最终形成1 - 2 - 3 - 4 - 5 - 6五、递归方法的优点与限制递归方法代码非常短也很优雅。但是它仍然存在一个问题虽然没有使用显式数组但是递归调用栈会消耗空间。在最坏情况下如果二叉树退化成链表递归深度可能达到n。因此递归方法的空间复杂度是O(h)其中h是二叉树高度。最坏情况下O(n)所以它还不是真正意义上的O(1)额外空间。六、原地算法寻找左子树最右节点题目进阶要求可以使用原地算法即 O(1) 额外空间展开这棵树吗要做到O(1)额外空间就不能使用数组也不能依赖递归栈。我们需要直接在原树上修改指针。对于当前节点curr如果它有左子树curr.left ! nullptr那么展开后的顺序应该是curr - curr.left - ... - curr.right也就是说需要把左子树移动到右边。但是原来的右子树不能丢失所以要先找到左子树中最靠右的节点predecessor。这个节点就是左子树按照先序展开后最后可以接上原右子树的位置。操作步骤如下1. 找到 curr 左子树中的最右节点 predecessor 2. predecessor-right curr-right 3. curr-right curr-left 4. curr-left nullptr 5. curr curr-right七、为什么要找左子树最右节点假设当前节点是11 / \ 2 5 / \ \ 3 4 6当前节点1的左子树是2 / \ 3 4右子树是5 \ 6按照先序遍历正确顺序应该是1 - 2 - 3 - 4 - 5 - 6所以我们应该把1的左子树整体移动到右边1 \ 2 / \ 3 4但是原来的右子树5 - 6不能丢需要接到左子树的最右节点4后面。连接后变成1 \ 2 / \ 3 4 \ 5 \ 6然后继续对2、3、4等节点做同样处理最终得到完整链表。八、O(1) 原地算法代码实现class Solution { public: void flatten(TreeNode* root) { TreeNode* curr root; while (curr ! nullptr) { if (curr-left ! nullptr) { TreeNode* predecessor curr-left; while (predecessor-right ! nullptr) { predecessor predecessor-right; } predecessor-right curr-right; curr-right curr-left; curr-left nullptr; } curr curr-right; } } };九、核心代码逐句解析1. 使用 curr 遍历整棵树TreeNode* curr root; while (curr ! nullptr) { ... }curr表示当前正在处理的节点。每次处理完当前节点后继续向右移动curr curr-right;因为最终展开后的链表只通过right指针连接。2. 判断当前节点是否存在左子树if (curr-left ! nullptr) { ... }如果当前节点没有左子树说明它已经符合链表方向可以直接处理下一个节点。如果当前节点有左子树则需要进行指针重排。3. 找到左子树的最右节点TreeNode* predecessor curr-left; while (predecessor-right ! nullptr) { predecessor predecessor-right; }这里的predecessor表示当前节点左子树中最靠右的节点。它的作用是承接当前节点原来的右子树。4. 将原右子树接到 predecessor 后面predecessor-right curr-right;这一步非常关键。如果不先保存原来的右子树它会在后续指针修改中丢失。5. 将左子树移动到右边curr-right curr-left;因为展开后的链表只能使用right指针所以需要将左子树整体移动到右指针上。6. 清空 left 指针curr-left nullptr;题目明确要求展开后的链表中所有节点的left指针必须为nullptr。十、完整推荐代码下面是推荐提交版本满足题目进阶要求额外空间为O(1)。#include iostream using namespace std; 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* curr root; while (curr ! nullptr) { if (curr-left ! nullptr) { TreeNode* predecessor curr-left; while (predecessor-right ! nullptr) { predecessor predecessor-right; } predecessor-right curr-right; curr-right curr-left; curr-left nullptr; } curr curr-right; } } };十一、算法流程总结对于每一个节点curr如果 curr 没有左子树 直接处理 curr.right 如果 curr 有左子树 找到 curr.left 中最右侧的节点 predecessor 将 curr 原来的右子树接到 predecessor.right 将 curr.left 移动到 curr.right 将 curr.left 置空 继续处理 curr.right可以概括为左子树搬到右边 原右子树接到左子树最右端 当前节点左指针置空 继续向右处理十二、复杂度分析时间复杂度对于每个节点我们最多会访问若干次。从整体来看算法在原树结构上不断向右推进并进行局部指针调整。时间复杂度为O(n)其中n是二叉树节点数量。空间复杂度该方法没有使用数组、栈、队列也没有使用递归。只使用了curr和predecessor两个指针变量。因此空间复杂度为O(1)这也正是题目进阶要求的解法。十三、递归法与原地法对比方法思路时间复杂度空间复杂度是否满足进阶先序遍历保存节点先遍历再重连O(n)O(n)否递归反向构造右、左、根反向连接O(n)O(h)严格来说否原地指针重排找左子树最右节点并接上右子树O(n)O(1)是在实际刷题中最推荐掌握的是第三种方法也就是原地指针重排法。十四、常见错误总结错误一直接覆盖 right导致右子树丢失错误写法curr-right curr-left; curr-left nullptr;这样会导致当前节点原来的右子树丢失。正确做法是先找到左子树最右节点并把原右子树接上去predecessor-right curr-right; curr-right curr-left; curr-left nullptr;错误二忘记将 left 置空展开后的链表要求所有节点的left指针都为nullptr。如果只移动右指针而不清空左指针结果不符合题目要求。错误三递归法误以为是 O(1) 空间递归写法虽然没有显式使用额外数组但是递归调用栈仍然占用空间。因此递归法空间复杂度是O(h)只有迭代指针重排法才是真正的O(1)额外空间。十五、为什么该算法符合先序遍历顺序对于任意节点curr先序遍历顺序是curr - 左子树 - 右子树原地算法做的事情正是curr.right curr.left 左子树最右节点.right 原 curr.right curr.left nullptr也就是说它把结构改造成curr - 左子树 - 原右子树这与先序遍历顺序完全一致。然后继续沿着right指针处理下一个节点。所以最终整棵树会被展开成一条符合先序遍历顺序的链表。十六、总结LeetCode 114「二叉树展开为链表」是一道典型的二叉树结构改造题。它考查的重点不是普通遍历而是如何在不创建新节点的情况下重新组织原有节点之间的指针关系。本题最核心的思想是对于每个节点 如果存在左子树 就将左子树移动到右边 再把原来的右子树接到左子树的最右节点后面。最终推荐使用原地指针重排法它的优势是时间复杂度O(n) 空间复杂度O(1) 符合题目进阶要求 代码简洁思路清晰这道题非常适合理解二叉树中的先序遍历结构转换也是学习树形结构原地修改的重要题目。