LeetCode 题解工作台
二叉树展开为链表
给你二叉树的根结点 root ，请你将它展开为一个单链表： 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。 展开后的单链表应该与二叉树 先序遍历 顺序相同。 示例 1： 输入： root = [1,2,5,3,4,null…
5
题型
7
代码语言
3
相关题
当前训练重点
中等 · 链表指针操作
答案摘要
先序遍历的访问顺序是“根、左子树、右子树”，左子树最后一个节点访问完后，接着会访问根节点的右子树节点。 因此，对于当前节点，如果其左子节点不为空，我们找到左子树的最右节点，作为前驱节点，然后将当前节点的右子节点赋给前驱节点的右子节点。然后将当前节点的左子节点赋给当前节点的右子节点，并将当前节点的左子节点置为空。然后将当前节点的右子节点作为下一个节点，继续处理，直至所有节点处理完毕。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 链表指针操作 题型思路
题目描述
给你二叉树的根结点 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
进阶：你可以使用原地算法（O(1) 额外空间）展开这棵树吗？
解题思路
方法一：寻找前驱节点
先序遍历的访问顺序是“根、左子树、右子树”，左子树最后一个节点访问完后，接着会访问根节点的右子树节点。
因此，对于当前节点，如果其左子节点不为空，我们找到左子树的最右节点，作为前驱节点，然后将当前节点的右子节点赋给前驱节点的右子节点。然后将当前节点的左子节点赋给当前节点的右子节点，并将当前节点的左子节点置为空。然后将当前节点的右子节点作为下一个节点，继续处理，直至所有节点处理完毕。
时间复杂度 ，其中 是树中节点的个数。空间复杂度 。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def flatten(self, root: Optional[TreeNode]) -> None:
"""
Do not return anything, modify root in-place instead.
"""
while root:
if root.left:
pre = root.left
while pre.right:
pre = pre.right
pre.right = root.right
root.right = root.left
root.left = None
root = root.right
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) because each node is visited once during pre-order traversal. Space complexity can be O(h) for recursion stack or O(n) for an explicit stack, or O(1) using the Morris traversal method. The provided complexities depend on the approach chosen, but all ensure linear processing relative to the number of nodes in the tree. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Do you see how flattening in pre-order affects the linked list pointer reassignment?
- question_mark
Can you implement this in-place without using extra nodes or arrays?
- question_mark
Will you correctly handle edge cases such as null or single-node trees while preserving order?
常见陷阱
外企场景- error
Forgetting to nullify the left child after moving the left subtree to the right can break the flattened structure.
- error
Incorrectly appending the original right subtree may lead to nodes being skipped or duplicated.
- error
Using a stack incorrectly may reverse the order of nodes, violating pre-order traversal sequence.
进阶变体
外企场景- arrow_right_alt
Flatten to a doubly-linked list preserving pre-order sequence with both next and previous pointers.
- arrow_right_alt
Flatten the tree in post-order instead of pre-order, testing pointer reassignment logic differently.
- arrow_right_alt
Flatten a n-ary tree to a linked list while maintaining pre-order traversal for multiple children per node.