企业官网建设流程全解析

LeetCode 114. 二叉树展开为链表 — Python3 实现

题目要求

将二叉树原地（in-place）展开为单链表，链表顺序为先序遍历顺序，使用right指针作为链表的next指针。

思路一：递归（后序展开）O(n)O(n)O(n)

从下往上处理：先把左右子树分别展开成链表，然后把右子树"挂"到左子树链表的末尾，再把整棵左子树挂到根的右边。

# 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 = rightclassSolution:defflatten(self,root:Optional[TreeNode])->None:""" Do not return anything, modify root in-place instead. """defflatten_and_return_tail(node):"""将子树展开为链表，返回链表尾节点"""ifnotnode:returnNone# 叶子节点：自己就是尾节点ifnotnode.leftandnotnode.right:returnnode left_tail=flatten_and_return_tail(node.left)# 展开左子树right_tail=flatten_and_return_tail(node.right)# 展开右子树ifleft_tail:# 左子树链表末尾接右子树left_tail.right=node.right node.right=node.left node.left=None# 尾节点：优先右子树的尾，否则左子树的尾returnright_tailorleft_tail flatten_and_return_tail(root)

时间复杂度：O(n)，每个节点访问一次空间复杂度：O(h)，递归栈深度（h 为树高，最坏 O(n)）

思路二：迭代（找左子树最右节点）O(1)O(1)O(1)额外空间

对当前节点，若存在左子树，则找到左子树的最右节点，把右子树挂到它后面，再将左子树移到右边：

classSolution:defflatten(self,root:Optional[TreeNode])->None:curr=rootwhilecurr:ifcurr.left:# 找到左子树的最右节点predecessor=curr.leftwhilepredecessor.right:predecessor=predecessor.right# 将右子树接到左子树最右节点之后predecessor.right=curr.right# 左子树移到右边curr.right=curr.left curr.left=None# 移动到下一个节点（即原来的左子树根）curr=curr.right

时间复杂度：O(n)空间复杂度：O(1)，无需递归栈

思路三：反向先序遍历（Morris 思想变体）

利用先序遍历的逆序（右 → 左 → 根），逐个把节点接到prev的右边：

classSolution:defflatten(self,root:Optional[TreeNode])->None:prev=Nonedefdfs(node):nonlocalprevifnotnode:returndfs(node.right)# 先处理右子树dfs(node.left)# 再处理左子树# 处理根：把 prev 接到当前节点的右边node.right=prev node.left=Noneprev=node dfs(root)

时间复杂度：O(n)空间复杂度：O(h)

关键点总结

1. 顺序陷阱：链表顺序是先序（根 → 左 → 右），不是中序，别搞混。
2. 思路二的精髓：左子树最右节点正是"先序遍历中左子树的最后一个节点"，所以它后面接右子树刚好保持先序顺序——这一步想清楚，代码就是顺势写出来的。
3. 原地修改：三种方法都只修改指针，不新建节点，满足 in-place 要求。
4. 示例：树[1,2,5,3,4,null,6]展开为1 → 2 → 3 → 4 → 5 → 6✅