LeetCode 热题 100 114. 二叉树展开为链表

LeetCode 热题 100 | 114. 二叉树展开为链表

大家好，今天我们来解决一道经典的二叉树问题——二叉树展开为链表。这道题在 LeetCode 上被标记为中等难度，要求将二叉树展开为一个单链表，展开后的单链表应该与二叉树的先序遍历顺序相同。

---

问题描述

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

提示：

• 树中结点数在范围 [0, 2000] 内
• -100 <= Node.val <= 100

---

解题思路

核心思想

1. 递归展开：

   • 使用递归方法，先序遍历二叉树，将每个节点的左子树和右子树展开为链表。
   • 将左子树的链表连接到当前节点的右子树上，然后将右子树的链表连接到左子树链表的末尾。

2. 原地展开：

   • 通过递归调用，原地修改节点的指针，避免使用额外的空间。

---

Python代码实现

class Solution:def flatten(self, root: TreeNode) -> None:"""Do not return anything, modify root in-place instead."""def flatten_tree(node):if not node:return None# 递归展开左子树和右子树left_tail = flatten_tree(node.left)right_tail = flatten_tree(node.right)# 如果有左子树，将其连接到右子树的位置if left_tail:left_tail.right = node.rightnode.right = node.leftnode.left = None# 返回当前子树的尾节点return right_tail or left_tail or nodeflatten_tree(root)

代码解析

1. 递归函数：

   • 定义一个递归函数 flatten_tree，用于展开以某个节点为根的子树。
   • 如果当前节点为空，返回 None。

2. 递归展开左右子树：

   • 递归调用 flatten_tree，分别展开当前节点的左子树和右子树，返回左子树和右子树的尾节点。

3. 连接左子树和右子树：

   • 如果左子树不为空，将左子树的尾节点连接到右子树的头节点。
   • 将当前节点的右子树指向左子树的头节点。
   • 将当前节点的左子树设置为 None。

4. 返回尾节点：

   • 返回当前子树的尾节点，用于连接后续的子树。

5. 主函数：

   • 调用 flatten_tree(root)，从根节点开始展开整个二叉树。

---

复杂度分析

• 时间复杂度：O(n)，其中 n 是二叉树的节点数。每个节点恰好被访问一次。
• 空间复杂度：O(log n)，递归调用栈的深度最多为树的高度，对于平衡树为 O(log n)，对于非平衡树可能达到 O(n)。

---

示例运行

示例 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]

---

总结

通过递归方法，我们可以高效地将二叉树展开为单链表。递归展开左右子树，并将左子树连接到右子树的位置，最终实现原地展开。希望这篇题解对大家有所帮助，如果有任何问题，欢迎在评论区留言讨论！

关注我，获取更多算法题解和编程技巧！