二叉树展开为链表（二叉树原地展开为链表）

# 简介在计算机科学中，二叉树是一种重要的数据结构，它由节点组成，每个节点最多有两个子节点：左子节点和右子节点。二叉树的遍历、操作和转换是算法设计中的常见任务。本文将介绍一种经典问题——如何将一个二叉树展开为链表。我们将从问题背景出发，逐步深入到解决方案，并通过代码实现来展示这一过程。---## 多级标题1. 问题背景 2. 解决思路 3. 实现步骤 4. 示例分析 5. 时间与空间复杂度 ---## 1. 问题背景给定一个二叉树，将其展开为单向链表。展开后的链表应该保持原有的节点顺序，即前序遍历的顺序。具体来说，对于一棵二叉树：```1/ \2 5/ \ \ 3 4 6 ```展开后应变为： ``` 1 -> 2 -> 3 -> 4 -> 5 -> 6 ```这个问题的关键在于如何在不使用额外存储的情况下，高效地完成这一转换。---## 2. 解决思路要将二叉树展开为链表，我们需要考虑以下几点：-

前序遍历

：展开后的链表需要保持前序遍历的顺序。 -

原地修改

：为了节省空间，我们希望尽可能避免使用额外的数据结构。 -

递归方法

：利用递归的方式处理左右子树，并将它们连接起来。核心思想是将右子树移动到左子树的最右侧节点之后，然后将左子树移到根节点的右边，最后将根节点的左指针置为空。---## 3. 实现步骤以下是具体的实现步骤：1.

检查特殊情况

：如果当前节点为空或没有左右子节点，则直接返回。 2.

递归处理右子树

：首先递归处理右子树。 3.

找到左子树的最右侧节点

：在左子树中找到最后一个节点（最右侧）。 4.

连接右子树

：将右子树挂接到左子树的最右侧节点上。 5.

调整指针

：将左子树移到右边，同时将左指针置空。 6.

继续递归

：对下一个节点重复上述步骤。---## 4. 示例分析假设输入的二叉树如下：```1/ \2 5/ \ \ 3 4 6 ```执行步骤如下：1. 将右子树 `5 -> 6` 移动到左子树的最右侧节点 `4` 后面。 2. 左子树 `2 -> 3 -> 4` 被移到根节点 `1` 的右边。 3. 最终结果为：`1 -> 2 -> 3 -> 4 -> 5 -> 6`。---## 5. 时间与空间复杂度-

时间复杂度

：O(n)，其中 n 是二叉树中的节点数。每个节点只访问一次。 -

空间复杂度

：O(h)，其中 h 是二叉树的高度。递归调用栈的空间取决于树的高度。---## 代码实现以下是 Python 的代码实现：```python class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef flatten(root: TreeNode) -> None:if not root:return# 递归处理右子树flatten(root.right)# 保存左子树temp_left = root.left# 将左子树移动到右边root.left = Noneroot.right = temp_left# 找到左子树的最右侧节点while temp_left:root = temp_lefttemp_left = root.right ```---通过以上步骤和代码，我们可以高效地将二叉树展开为链表，同时满足时间和空间效率的要求。

简介在计算机科学中，二叉树是一种重要的数据结构，它由节点组成，每个节点最多有两个子节点：左子节点和右子节点。二叉树的遍历、操作和转换是算法设计中的常见任务。本文将介绍一种经典问题——如何将一个二叉树展开为链表。我们将从问题背景出发，逐步深入到解决方案，并通过代码实现来展示这一过程。---

多级标题1. 问题背景 2. 解决思路 3. 实现步骤 4. 示例分析 5. 时间与空间复杂度 ---

1. 问题背景给定一个二叉树，将其展开为单向链表。展开后的链表应该保持原有的节点顺序，即前序遍历的顺序。具体来说，对于一棵二叉树：```1/ \2 5/ \ \ 3 4 6 ```展开后应变为： ``` 1 -> 2 -> 3 -> 4 -> 5 -> 6 ```这个问题的关键在于如何在不使用额外存储的情况下，高效地完成这一转换。---

2. 解决思路要将二叉树展开为链表，我们需要考虑以下几点：- **前序遍历**：展开后的链表需要保持前序遍历的顺序。 - **原地修改**：为了节省空间，我们希望尽可能避免使用额外的数据结构。 - **递归方法**：利用递归的方式处理左右子树，并将它们连接起来。核心思想是将右子树移动到左子树的最右侧节点之后，然后将左子树移到根节点的右边，最后将根节点的左指针置为空。---

3. 实现步骤以下是具体的实现步骤：1. **检查特殊情况**：如果当前节点为空或没有左右子节点，则直接返回。 2. **递归处理右子树**：首先递归处理右子树。 3. **找到左子树的最右侧节点**：在左子树中找到最后一个节点（最右侧）。 4. **连接右子树**：将右子树挂接到左子树的最右侧节点上。 5. **调整指针**：将左子树移到右边，同时将左指针置空。 6. **继续递归**：对下一个节点重复上述步骤。---

4. 示例分析假设输入的二叉树如下：```1/ \2 5/ \ \ 3 4 6 ```执行步骤如下：1. 将右子树 `5 -> 6` 移动到左子树的最右侧节点 `4` 后面。 2. 左子树 `2 -> 3 -> 4` 被移到根节点 `1` 的右边。 3. 最终结果为：`1 -> 2 -> 3 -> 4 -> 5 -> 6`。---

5. 时间与空间复杂度- **时间复杂度**：O(n)，其中 n 是二叉树中的节点数。每个节点只访问一次。 - **空间复杂度**：O(h)，其中 h 是二叉树的高度。递归调用栈的空间取决于树的高度。---

代码实现以下是 Python 的代码实现：```python class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef flatten(root: TreeNode) -> None:if not root:return

递归处理右子树flatten(root.right)

保存左子树temp_left = root.left

将左子树移动到右边root.left = Noneroot.right = temp_left

找到左子树的最右侧节点while temp_left:root = temp_lefttemp_left = root.right ```---通过以上步骤和代码，我们可以高效地将二叉树展开为链表，同时满足时间和空间效率的要求。