（LeetCode-Hot100）114. 二叉树展开为链表

Ne0inhk

— 7 min read
（LeetCode-Hot100）114. 二叉树展开为链表

问题简介

LeetCode 114. 二叉树展开为链表

题解github地址: https://github.com/swf2020/LeetCode-Hot100-Solutions

题目描述

给你二叉树的根结点 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]

📌 图示说明（以示例1为例）：

原始二叉树：

 1 / \ 2 5 / \ \ 3 4 6

展开后链表（只看 right 指针）：

1 → 2 → 3 → 4 → 5 → 6

解题思路

✅ 方法一：递归 + 先序遍历（后序处理）

💡 核心思想：
我们希望按照先序遍历的顺序重新组织节点。但如果我们直接在遍历时修改指针，会丢失子树信息。因此采用后序遍历的方式，从下往上处理。

步骤：

  1. 递归展开左子树和右子树。
  2. 将当前节点的右子树暂存。
  3. 将当前节点的右子树设为左子树（此时左子树已展开为链表）。
  4. 将左子树置空。
  5. 找到当前右子树（原左子树）的最右节点，将其 right 指向暂存的原右子树。
这种方法保证了在处理当前节点时，左右子树已经各自被展平为链表。

✅ 方法二：迭代（使用栈模拟先序遍历）

💡 核心思想：
用栈模拟先序遍历，同时在遍历过程中调整指针。

步骤：

  1. 使用栈存储待访问节点。
  2. 每次弹出一个节点，将其右、左子节点依次压入栈（因为栈是 LIFO，所以先压右再压左，保证先访问左）。
  3. 在遍历过程中，将前一个节点的 right 指向当前节点，并将 left 置空。
注意：需要记录前一个访问的节点。

✅ 方法三：Morris 遍历（空间复杂度 O(1)）

💡 核心思想：
利用 Morris 先序遍历的思想，在不使用额外空间的情况下完成展开。

关键观察：
在先序遍历中，左子树的最后一个节点（即左子树最右节点）的下一个节点是当前节点的右子节点。

步骤：

  1. 对于当前节点：
    • 如果有左子树：
      • 找到左子树的最右节点（前驱节点）。
      • 将前驱节点的 right 指向当前节点的右子树。
      • 将当前节点的 right 指向左子树。
      • 将当前节点的 left 置空。
    • 移动到 right 节点继续处理。
这是最优解，时间 O(n)，空间 O(1)。

代码实现

// Java 实现/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */// 方法一：递归（后序）classSolution{publicvoidflatten(TreeNode root){if(root ==null)return;// 递归展开左右子树flatten(root.left);flatten(root.right);// 保存右子树TreeNode right = root.right;// 将左子树移到右边 root.right = root.left; root.left =null;// 找到当前右子树的最右节点TreeNode curr = root;while(curr.right !=null){ curr = curr.right;}// 连接原右子树 curr.right = right;}}// 方法二：迭代（栈）classSolution2{publicvoidflatten(TreeNode root){if(root ==null)return;Stack<TreeNode> stack =newStack<>(); stack.push(root);TreeNode prev =null;while(!stack.isEmpty()){TreeNode curr = stack.pop();if(prev !=null){ prev.right = curr; prev.left =null;}// 先压右，再压左（保证先处理左）if(curr.right !=null){ stack.push(curr.right);}if(curr.left !=null){ stack.push(curr.left);} prev = curr;}}}// 方法三：Morris 遍历（O(1) 空间）classSolution3{publicvoidflatten(TreeNode root){TreeNode curr = root;while(curr !=null){if(curr.left !=null){// 找到左子树的最右节点TreeNode predecessor = curr.left;while(predecessor.right !=null){ predecessor = predecessor.right;}// 将原右子树接到前驱节点后面 predecessor.right = curr.right;// 左子树移到右边 curr.right = curr.left; curr.left =null;} curr = curr.right;}}}
// Go 实现/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */// 方法一：递归（后序）funcflatten(root *TreeNode){if root ==nil{return}// 递归展开左右子树flatten(root.Left)flatten(root.Right)// 保存右子树 right := root.Right // 将左子树移到右边 root.Right = root.Left root.Left =nil// 找到当前右子树的最右节点 curr := root for curr.Right !=nil{ curr = curr.Right }// 连接原右子树 curr.Right = right }// 方法二：迭代（栈）funcflatten2(root *TreeNode){if root ==nil{return} stack :=[]*TreeNode{root}var prev *TreeNode forlen(stack)>0{ curr := stack[len(stack)-1] stack = stack[:len(stack)-1]if prev !=nil{ prev.Right = curr prev.Left =nil}// 先压右，再压左if curr.Right !=nil{ stack =append(stack, curr.Right)}if curr.Left !=nil{ stack =append(stack, curr.Left)} prev = curr }}// 方法三：Morris 遍历（O(1) 空间）funcflatten3(root *TreeNode){ curr := root for curr !=nil{if curr.Left !=nil{// 找到左子树的最右节点 predecessor := curr.Left for predecessor.Right !=nil{ predecessor = predecessor.Right }// 将原右子树接到前驱节点后面 predecessor.Right = curr.Right // 左子树移到右边 curr.Right = curr.Left curr.Left =nil} curr = curr.Right }}

示例演示

以 root = [1,2,5,3,4,null,6] 为例，展示 方法一（递归） 的执行过程：

 初始： 1 / \ 2 5 / \\ \ 3 4 6 递归调用 flatten(2): flatten(3) → 叶子，不变 flatten(4) → 叶子，不变 处理 2: right = null（原2的右子树是4，但flatten(4)后4的right=null） 2.right = 3（原左子树） 2.left = null 找到 3 的最右（就是3），3.right = 4 → 2 → 3 → 4 递归调用 flatten(5): flatten(null) flatten(6) 处理 5: 5.right = null（无左子树） → 5 → 6 回到 root=1: right = 5→6 1.right = 2→3→4 1.left = null 找到 4（最右），4.right = 5→6 最终：1→2→3→4→5→6

✅ 结果正确！

答案有效性证明

我们需证明：最终链表的顺序等于原树的先序遍历序列。

  • 方法一（递归）：
    由于我们先递归处理左右子树（使其变为先序链表），再将“左链表”接在根后，“右链表”接在左链表后，整体顺序为 [root] + [left preorder] + [right preorder]，符合先序定义。
  • 方法二（迭代）：
    栈模拟的就是标准先序遍历（根→左→右），且每次将前一个节点的 right 指向当前节点，因此顺序一致。
  • 方法三（Morris）：
    Morris 先序遍历本身就能保证访问顺序正确，而我们在访问每个节点时立即调整指针，确保结构同步更新。

因此，三种方法均能正确生成先序链表。

复杂度分析

方法时间复杂度空间复杂度说明
递归O(n)O(n)递归栈深度最坏为 n（退化为链表）
迭代（栈）O(n)O(n)栈最多存储 n 个节点
Morris 遍历O(n)O(1)利用树本身结构，无需额外空间
⚠️ 注意：虽然 Morris 方法空间最优，但会临时修改树结构（不过最终恢复为链表，符合题目要求）。

问题总结

  • ❌ 常见错误：在先序遍历过程中直接修改指针，导致子树丢失。
  • ✅ 关键洞察：必须在处理当前节点前，确保左右子树已展平；或使用 Morris 技巧避免信息丢失。
  • 💡 最优解：Morris 遍历，空间复杂度 O(1)，适合面试展示高级技巧。
  • 📌 适用场景：
    • 递归：代码简洁，适合理解逻辑。
    • 迭代：避免递归栈溢出（对极深树更安全）。
    • Morris：追求极致空间效率。
本题是树结构原地转换的经典问题，掌握其思想有助于解决类似“展开”、“拉直”类题目。
Could not load content