LeetCode 114. 二叉树展开为链表 — Python3 实现题目要求将二叉树原地in-place展开为单链表链表顺序为先序遍历顺序使用right指针作为链表的next指针。思路一递归后序展开O(n)O(n)O(n)从下往上处理先把左右子树分别展开成链表然后把右子树挂到左子树链表的末尾再把整棵左子树挂到根的右边。# Definition for a binary tree node.# class TreeNode:# def __init__(self, val0, leftNone, rightNone):# 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_tailflatten_and_return_tail(node.left)# 展开左子树right_tailflatten_and_return_tail(node.right)# 展开右子树ifleft_tail:# 左子树链表末尾接右子树left_tail.rightnode.right node.rightnode.left node.leftNone# 尾节点优先右子树的尾否则左子树的尾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:currrootwhilecurr:ifcurr.left:# 找到左子树的最右节点predecessorcurr.leftwhilepredecessor.right:predecessorpredecessor.right# 将右子树接到左子树最右节点之后predecessor.rightcurr.right# 左子树移到右边curr.rightcurr.left curr.leftNone# 移动到下一个节点即原来的左子树根currcurr.right时间复杂度O(n)空间复杂度O(1)无需递归栈思路三反向先序遍历Morris 思想变体利用先序遍历的逆序右 → 左 → 根逐个把节点接到prev的右边classSolution:defflatten(self,root:Optional[TreeNode])-None:prevNonedefdfs(node):nonlocalprevifnotnode:returndfs(node.right)# 先处理右子树dfs(node.left)# 再处理左子树# 处理根把 prev 接到当前节点的右边node.rightprev node.leftNoneprevnode dfs(root)时间复杂度O(n)空间复杂度O(h)关键点总结顺序陷阱链表顺序是先序根 → 左 → 右不是中序别搞混。思路二的精髓左子树最右节点正是先序遍历中左子树的最后一个节点所以它后面接右子树刚好保持先序顺序——这一步想清楚代码就是顺势写出来的。原地修改三种方法都只修改指针不新建节点满足 in-place 要求。示例树[1,2,5,3,4,null,6]展开为1 → 2 → 3 → 4 → 5 → 6✅