二叉树展开为单链表
问题分析
将一棵二叉树原地展开为一个单链表，链表节点顺序等于二叉树的先序遍历（根→左→右）。展开后每个节点的左指针必须为 null，右指针指向下一个节点。
解题思路
方法一（递归后序反向处理）：
- 使用递归函数返回当前子树展开后的“尾节点”。
- 对于当前节点 root：先递归展开右子树，得到 rightTail；再递归展开左子树，得到 leftTail。
P4063.二叉树展开为链表
在线刷题
给你二叉树的根结点 root，请你将它展开为一个单链表：
- 展开后的单链表仍然使用
TreeNode
right 指针指向链表中下一个节点，left 始终为 null- 链表顺序必须与二叉树先序遍历顺序相同
样例1
输入
1 2 5 3 4 null 6
输出
1 null 2 null 3 null 4 null 5 null 6
样例2
输入
0
输出
0
提示
- 树中结点数在范围 [0,2000] 内
- −100<=Node.val<=100
方法一：自底向上的 DFS
受到LeetCode 104. 二叉树的最大深度中方法二：自底向上的DFS的启发，我们考虑拆分子问题:
当前节点展开结果 = 当前节点 + 左子树链 + 右子树链
例如样例1 ： 从根节点开始，一个“自底向上”的想法是：
1.递归进入左子树，构造左链：left_tree = 2->3->4
2.递归进入右子树，构造右链：right_tree = 5->6
3.最后拼成：1->2->3->4->5->6
由于 左链 + 右链 这一步需要让 左链 的尾节点(或者说叶子节点)连到右链的根节点, 所以递归函数需要返回的是链的叶子节点(或者说尾节点) tail
动画模拟
这里用两个样例来模拟一遍算法，帮助大家更好理解代码逻辑，请逐帧观看+分析👇
代码实现
from typing import Optional
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:
def flatten_tail(node: Optional[TreeNode]) -> Optional[TreeNode]:
# 空树没有尾节点，直接返回 None
if node is None:
return None
# 先保存当前节点原本的左子树和右子树的根节点
left_head = node.left
right_head = node.right
# 递归展开左右子树成链
left_tail = flatten_tail(node.left)
right_tail = flatten_tail(node.right)
# root -> 左链表 -> 右链表
# 如果左链不为空，则拼接左链和右链
if left_head:
# 根 + 左链
node.right = left_head
# 题目要求拉平后的树不能有左指针
node.left = None
# 左链 + 右链
left_tail.right = right_head
# 返回尾节点
# 如果原来有右子树，那么最终尾节点一定是右链表的尾节点
# 如果没有右子树但有左子树，那么最终尾节点是左链表的尾节点
# 如果左右子树都没有，那么当前 node 自己就是尾节点
return right_tail or left_tail or node
flatten_tail(root)
def build_tree(tree_arr):
if not tree_arr or tree_arr[0] is None:
return None
q = []
rt = TreeNode(tree_arr[0])
q.append(rt)
index = 1
while q and index < len(tree_arr):
node = q.pop(0)
if index < len(tree_arr) and tree_arr[index] is not None:
node.left = TreeNode(tree_arr[index])
q.append(node.left)
index += 1
if index < len(tree_arr) and tree_arr[index] is not None:
node.right = TreeNode(tree_arr[index])
q.append(node.right)
index += 1
return rt
def serialize_flattened(root: Optional[TreeNode]) -> str:
# 按题目输出风格：val null val null ...
out = []
cur = root
while cur is not None:
out.append(str(cur.val))
if cur.right is not None:
out.append("null")
cur = cur.right
return " ".join(out)
def main():
# ACM 输入：一行层序，null 表示空节点
# 例如：1 2 5 3 4 null 6
tokens = input().split()
tree_arr = []
for x in tokens:
if x == "null":
tree_arr.append(None)
else:
tree_arr.append(int(x))
rt = build_tree(tree_arr)
Solution().flatten(rt)
print(serialize_flattened(rt))
if __name__ == "__main__":
main()
面试问答
1. 本题的核心思路是什么？
从根节点开始递归，每次先递归展开左右子树成链，再按 node -> left -> right 拼起来。为了能够正常拼接，需要让递归返回尾节点 tail
每个节点只处理一次，时间复杂度 O(n)。空间主要是递归栈，最坏 O(n)（链状树），平衡树约 O(log n)。
