湛江建设局网站,网站编程电子书,aspnet东莞网站建设多少钱,oa办公系统软件哪家好LeetCode 热题100 | 226. 翻转二叉树
大家好#xff0c;今天我们来解决一道经典的算法题——翻转二叉树。这道题在 LeetCode 上被标记为简单难度#xff0c;要求我们翻转一棵二叉树#xff0c;并返回其根节点。下面我将详细讲解解题思路#xff0c;并附上 Python 代码实现…LeetCode 热题100 | 226. 翻转二叉树
大家好今天我们来解决一道经典的算法题——翻转二叉树。这道题在 LeetCode 上被标记为简单难度要求我们翻转一棵二叉树并返回其根节点。下面我将详细讲解解题思路并附上 Python 代码实现。 题目描述
给定一棵二叉树的根节点 root翻转这棵二叉树并返回其根节点。
示例
输入root [4,2,7,1,3,6,9]
输出[4,7,2,9,6,3,1]解题思路
翻转二叉树的核心思想是交换每个节点的左右子树。我们可以通过递归或迭代的方式来实现。
核心思想 递归法 递归地翻转左子树和右子树。交换当前节点的左右子树。 迭代法BFS 使用队列进行层次遍历逐层交换每个节点的左右子树。 代码实现
方法 1递归法
class TreeNode:def __init__(self, val0, leftNone, rightNone):self.val valself.left leftself.right rightdef invertTree(root)::type root: TreeNode:rtype: TreeNodeif not root:return None# 递归翻转左右子树left invertTree(root.left)right invertTree(root.right)# 交换当前节点的左右子树root.left rightroot.right leftreturn root方法 2迭代法BFS
from collections import dequedef invertTree(root)::type root: TreeNode:rtype: TreeNodeif not root:return Nonequeue deque([root]) # 使用队列存储节点while queue:node queue.popleft() # 弹出当前节点# 交换当前节点的左右子树node.left, node.right node.right, node.left# 将左右子节点加入队列if node.left:queue.append(node.left)if node.right:queue.append(node.right)return root代码解析
递归法 递归终止条件 如果当前节点为空返回 None。 递归翻转左右子树 递归地翻转左子树和右子树。 交换当前节点的左右子树 将当前节点的左子树指向翻转后的右子树右子树指向翻转后的左子树。 返回根节点 返回翻转后的二叉树的根节点。
迭代法BFS 初始化 如果根节点为空直接返回 None。使用队列存储节点初始时将根节点加入队列。 遍历队列 弹出当前节点交换其左右子树。将当前节点的左右子节点加入队列。 返回根节点 遍历结束后返回翻转后的二叉树的根节点。 复杂度分析
时间复杂度O(n)其中 n 是二叉树的节点数。每个节点被访问一次。空间复杂度 递归法O(h)其中 h 是二叉树的高度递归调用栈的深度为树的高度。迭代法O(n)队列的最大空间为树的宽度。 示例运行
示例 1
# 创建二叉树 [4,2,7,1,3,6,9]
root TreeNode(4)
root.left TreeNode(2)
root.right TreeNode(7)
root.left.left TreeNode(1)
root.left.right TreeNode(3)
root.right.left TreeNode(6)
root.right.right TreeNode(9)# 翻转二叉树
inverted_root invertTree(root)# 层序遍历输出结果
def levelOrder(root):if not root:return []result []queue deque([root])while queue:level_size len(queue)level_nodes []for _ in range(level_size):node queue.popleft()level_nodes.append(node.val)if node.left:queue.append(node.left)if node.right:queue.append(node.right)result.append(level_nodes)return resultprint(levelOrder(inverted_root)) # 输出: [[4], [7, 2], [9, 6, 3, 1]]示例 2
# 创建二叉树 [2,1,3]
root TreeNode(2)
root.left TreeNode(1)
root.right TreeNode(3)# 翻转二叉树
inverted_root invertTree(root)# 层序遍历输出结果
print(levelOrder(inverted_root)) # 输出: [[2], [3, 1]]示例 3
# 创建空二叉树 []
root None# 翻转二叉树
inverted_root invertTree(root)# 层序遍历输出结果
print(levelOrder(inverted_root)) # 输出: []总结
通过递归或迭代的方式我们可以高效地翻转二叉树。递归法代码简洁但可能受递归深度限制迭代法使用队列进行层次遍历适合处理较大的树。希望这篇题解对你有帮助如果还有其他问题欢迎继续提问
关注我获取更多算法题解和编程技巧
