文章目录LeetCode 226. 翻转二叉树 —— BFS / 队列解法整体思路一个队列就够了第一版思路每次从队列中取出当前节点我踩的坑把 None 直接加入了队列为什么交换时却不用判断 None为什么 None 不需要加入队列一个例子为什么交换以后还是正确的整个 BFS 流程第一次循环第二次循环第三次循环最终代码还可以进一步简化交换复杂度分析这道题我学到的点总结LeetCode 226. 翻转二叉树 —— BFS / 队列解法前面已经做过几道二叉树相关的题对TreeNode、队列和 BFS 遍历稍微熟悉了一些。若是对他们还不熟悉推荐可以看看我前几个关于二叉树的帖子我尽量用自己能理解的方式解释了一下。譬如 DAY3LeetCode 104. 二叉树的最大深度另一个方法这道题看到以后我第一反应其实很直接翻转二叉树不就是把每一个节点的左孩子和右孩子交换吗例如4 / \ 2 7翻转以后4 / \ 7 2但不只是根节点需要交换。整棵树中每一个节点都要执行同样的操作取出一个节点 ↓ 交换它的左孩子和右孩子 ↓ 继续处理后面的节点所以这道题很适合继续使用前面学过的BFS 队列。整体思路一个队列就够了我一开始也想过要不要一个队列存左孩子一个队列存右孩子后来发现完全没有必要。因为我们真正处理的是当前这个节点本身。每次从队列中拿出一个节点nodeq.popleft()然后交换node.left node.right即可。处理完当前节点后再把它的孩子加入队列继续处理。所以一个队列就够了。第一版思路先处理特殊情况ifrootisNone:returnroot如果根节点就是空的直接返回。然后创建队列qdeque([root])这里的[root]表示创建一个只包含根节点的列表再用它初始化队列。也就是qdeque()q.append(root)的简写。每次从队列中取出当前节点nodeq.popleft()然后先保存它原来的左右孩子node_leftnode.left node_rightnode.right之后交换node.leftnode_right node.rightnode_left这就是当前节点的翻转。我踩的坑把None直接加入了队列我一开始直接写的是q.append(node_left)q.append(node_right)没有判断左右孩子是否存在。而 Python 的deque其实是允许放入None的。例如q.append(None)这本身不会报错。所以真正的问题是下一轮把None从队列中取出来以后程序还会把它当成一个 TreeNode 使用。例如nodeq.popleft()如果此时nodeisNone后面再执行node.left就会报错。因为None根本没有.left.right这些属性。所以错误发生的流程其实是某个节点没有左孩子 ↓ node.left None ↓ 把 None 加入队列 ↓ 下一轮 popleft() ↓ node None ↓ 继续访问 node.left ↓ 报错为什么交换时却不用判断 None这个地方我一开始有点疑惑。既然node.left可能是None那为什么交换的时候node.leftnode_right node.rightnode_left不需要先判断因为把None赋值给一个节点的left或right是完全合法的。比如node.leftNone只是表示当前节点没有左孩子。这和访问None.left是完全不同的事情。可以区分成node.left None这是合法的给当前节点的 left 属性赋值为 None。但是None.left是不合法的试图从 None 这个对象中访问 left 属性。所以赋值 None没问题。真正有问题的是把 None 当成 TreeNode 使用。为什么None不需要加入队列这里我一开始有一个疑问deque明明可以存None为什么这道题还要先判断左右孩子是否存在再决定要不要入队后来想清楚以后发现关键不在于None 能不能放进队列而在于这个元素后面还需不需要继续处理这道题中队列的作用是保存接下来还需要进行 “左右孩子交换” 的节点。每次nodeq.popleft()取出一个真实存在的节点然后执行node.left,node.rightnode.right,node.left如果某个孩子是None说明这个位置根本没有节点。既然没有节点也就不存在左孩子 右孩子更不需要进行交换。所以ifnode.left:q.append(node.left)ifnode.right:q.append(node.right)本质上是在筛选只把后面还需要继续处理的真实节点放进队列。可以理解成真实 TreeNode → 后面还要交换它自己的左右孩子 → 加入队列 None → 本身不是节点也没有左右孩子 → 不需要加入队列所以这道题里虽然q.append(None)语法上是允许的但从算法逻辑上没有必要。一个例子假设当前节点是5 / 3那么node.left是节点3而node.rightNone保存node_leftnode.left node_rightnode.right得到node_left 3 node_right None然后交换node.leftnode_right node.rightnode_left就变成5 \ 3也就是node.leftNonenode.right3这完全合法。所以交换的时候不需要判断None是否存在。为什么交换以后还是正确的这里还有一个容易绕的点。我们是先保存node_leftnode.left node_rightnode.right然后把原来的左右孩子加入队列ifnode_left:q.append(node_left)ifnode_right:q.append(node_right)最后再交换node.leftnode_right node.rightnode_left有人可能会疑惑我们加入队列的是“交换前”的左右孩子那后面还能正确处理吗可以。因为node_left node_right保存的不是左右“位置”而是两个具体的TreeNode对象。例如原来 4 / \ 2 7那么node_left节点2node_right节点7把它们加入队列q [2, 7]然后交换4 / \ 7 2虽然它们的位置变了但节点2还是节点2 节点7还是节点7队列中保存的仍然是这两个节点对象。下一轮继续处理它们自己的左右孩子即可。所以队列负责保存“接下来哪些节点还需要处理”并不关心它们现在位于父节点的左边还是右边。整个 BFS 流程假设原树4 / \ 2 7 / \ / \ 1 3 6 9一开始q [4]第一次循环弹出4保存左孩子 2 右孩子 7把存在的孩子加入队列q [2, 7]交换4 / \ 7 2第二次循环弹出2注意虽然节点2现在已经变成根节点4的右孩子但它仍然是同一个TreeNode(2)。它的左右孩子关系没有变还是可以指向正确的需要交换的节点。继续处理它2 / \ 1 3交换以后2 / \ 3 1同时把节点1和3加入队列。第三次循环处理7再交换它的左右孩子。如此循环直到队列为空。最终整棵树中的所有节点都被处理一次。最终代码fromcollectionsimportdequeclassSolution:definvertTree(self,root:Optional[TreeNode])-Optional[TreeNode]:ifrootisNone:returnroot qdeque([root])whileq:nodeq.popleft()node_leftnode.left node_rightnode.right# 只有真正存在的节点才需要继续处理ifnode_left:q.append(node_left)ifnode_right:q.append(node_right)# 交换当前节点的左右孩子node.leftnode_right node.rightnode_leftreturnroot还可以进一步简化交换Python 本身支持同时交换node.left,node.rightnode.right,node.left所以也可以写成fromcollectionsimportdequeclassSolution:definvertTree(self,root:Optional[TreeNode])-Optional[TreeNode]:ifrootisNone:returnroot qdeque([root])whileq:nodeq.popleft()node.left,node.rightnode.right,node.leftifnode.left:q.append(node.left)ifnode.right:q.append(node.right)returnroot这里交换以后再把新的左右孩子加入队列也一样可以。因为无论交换前还是交换后最终都还是那两个孩子节点只是左右位置发生了变化。复杂度分析设二叉树一共有n个节点。每个节点都会进入队列一次 弹出一次 交换一次左右孩子所以时间复杂度O(n)队列最坏情况下可能保存一整层的节点空间复杂度O(n)这道题我学到的点翻转二叉树的本质就是对每一个节点 交换 left 和 right一个队列就够了。队列只是负责保存接下来还有哪些节点需要处理deque可以保存None但这里没必要保存。因为None本身不需要继续处理。真正会报错的不是q.append(None)而是之后nodeNonenode.left因为None没有left属性。下面两件事要区分node.leftNone合法表示没有左孩子。但是None.left非法因为None不是TreeNode。队列里保存的是节点对象。即使交换以后节点从左边跑到右边它仍然是原来的那个TreeNode所以后续依然可以正常处理。总结这道题用 BFS 队列的思路其实很直接根节点入队 ↓ 弹出当前节点 ↓ 交换当前节点的左右孩子 ↓ 把存在的孩子加入队列 ↓ 继续处理下一个节点 ↓ 队列为空 ↓ 整棵树翻转完成和之前几道 BFS 题相比这道题更能说明BFS 不一定要一层一层做统计。有时候我们只是借助队列把整棵树中的每一个节点都访问一遍然后对每个节点执行相同操作即可。