【LeetCode刷题】翻转二叉树

给你一棵二叉树的根节点root，翻转这棵二叉树，并返回其根节点。

示例 1：

输入：root = [4,2,7,1,3,6,9]输出：[4,7,2,9,6,3,1]

示例 2：

输入：root = [2,1,3]输出：[2,3,1]

示例 3：

输入：root = []输出：[]

提示：

• 树中节点数目范围在[0, 100]内
• -100 <= Node.val <= 100

解题思路

翻转二叉树的本质是交换树中每个节点的左右子节点，采用递归策略实现：

1. 边界处理：若当前节点为空（root is None），直接返回空（无需翻转）；
2. 交换子节点：对当前非空节点，交换其left和right子节点；
3. 递归遍历：分别对交换后的左子节点、右子节点递归执行翻转操作；
4. 返回节点：完成当前节点及子树的翻转后，返回当前节点。

示例验证（以示例 1 为例）

输入树结构：root = [4,2,7,1,3,6,9]

1. 根节点4：交换左右子节点2和7，得到左子树7、右子树2；
2. 节点7：交换其左右子节点6和9；
3. 节点2：交换其左右子节点1和3；最终得到翻转后的树：[4,7,2,9,6,3,1]，与示例输出一致。

算法特性

• 时间复杂度：O(n)（需遍历树中所有n个节点，每个节点仅处理一次）；
• 空间复杂度：O(h)（h为树的高度，递归栈的深度由树高决定；最坏情况下树为链状，h=n）。

Python代码

from typing import Optional, List, Deque from collections import deque class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right class Solution: def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]: # 边界条件：空节点直接返回 if not root: return None # 交换当前节点的左右子节点 root.left, root.right = root.right, root.left # 递归翻转左子树和右子树 self.invertTree(root.left) self.invertTree(root.right) # 返回当前节点（已完成翻转） return root def build_tree(nums: List[Optional[int]]) -> Optional[TreeNode]: """层序遍历构建二叉树（适配LeetCode的数组表示法，None表示空节点）""" if not nums or nums[0] is None: return None root = TreeNode(nums[0]) q: Deque[TreeNode] = deque([root]) i = 1 while q and i < len(nums): cur_node = q.popleft() # 构建左子节点 if nums[i] is not None: cur_node.left = TreeNode(nums[i]) q.append(cur_node.left) i += 1 # 构建右子节点 if i < len(nums) and nums[i] is not None: cur_node.right = TreeNode(nums[i]) q.append(cur_node.right) i += 1 return root def print_tree(root: Optional[TreeNode]) -> List[Optional[int]]: """层序遍历打印二叉树（转回数组，方便查看翻转结果）""" if not root: return [] res = [] q: Deque[TreeNode] = deque([root]) while q: cur_node = q.popleft() if cur_node: res.append(cur_node.val) q.append(cur_node.left) q.append(cur_node.right) else: res.append(None) # 去除末尾的空节点，让结果更整洁 while res and res[-1] is None: res.pop() return res if __name__ == "__main__": nums = [4, 2, 7, 1, 3, 6, 9] # 原二叉树数组 root = build_tree(nums) print("翻转前的二叉树（层序）：", print_tree(root)) # 输出 [4,2,7,1,3,6,9] # 执行翻转 sol = Solution() invert_root = sol.invertTree(root) print("翻转后的二叉树（层序）：", print_tree(invert_root)) # 输出 [4,7,2,9,6,3,1]

LeetCode提交代码

# 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 invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]: # 边界条件：空节点直接返回 if not root: return None # 交换当前节点的左右子节点 root.left, root.right = root.right, root.left # 递归翻转左子树和右子树 self.invertTree(root.left) self.invertTree(root.right) # 返回当前节点（已完成翻转） return root

程序运行截图展示

总结

本文介绍如何翻转二叉树，即交换树中每个节点的左右子节点。采用递归策略：处理空节点直接返回；非空节点交换左右子节点后递归处理子树。示例验证显示输入[4,2,7,1,3,6,9]翻转后为[4,7,2,9,6,3,1]。算法时间复杂度O(n)，空间复杂度O(h)。提供Python实现代码，包括树构建和打印方法，以及LeetCode提交格式。核心思想是通过递归交换左右子树实现整棵树的翻转。