核心内容摘要
绿帽社：一场关于性别、观念与网络文化的深度探索
给你一棵二叉树的根节点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解题思路翻转二叉树的本质是交换树中每个节点的左右子节点采用递归策略实现边界处理若当前节点为空root is None直接返回空无需翻转交换子节点对当前非空节点交换其left和right子节点递归遍历分别对交换后的左子节点、右子节点递归执行翻转操作返回节点完成当前节点及子树的翻转后返回当前节点。
示例验证以示例 1 为例输入树结构root [4,2,7,1,3,6,9]根节点4交换左右子节点2和7得到左子树
右子树2节点7交换其左右子节点6和9节点2交换其左右子节点1和3最终得到翻转后的树[4,7,2,9,6,3,1]与示例输出一致。
算法特性时间复杂度O(n)需遍历树中所有n个节点每个节点仅处理一次空间复杂度O(h)h为树的高度递归栈的深度由树高决定最坏情况下树为链状hn。
Python代码from typing import Optional, List, Deque from collections import deque class TreeNode: def __init__(self, val0, leftNone, rightNone): 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, val0, leftNone, rightNone): # 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提交格式。
核心思想是通过递归交换左右子树实现整棵树的翻转。