DAY4：LeetCode 226. 翻转二叉树

LeetCode 226. 翻转二叉树 —— BFS / 队列解法

前面已经做过几道二叉树相关的题，对TreeNode、队列和 BFS 遍历稍微熟悉了一些。

若是对他们还不熟悉，推荐可以看看我前几个关于二叉树的帖子，我尽量用自己能理解的方式解释了一下。
譬如 DAY3：LeetCode 104. 二叉树的最大深度（另一个方法）

这道题看到以后，我第一反应其实很直接：

翻转二叉树，不就是把每一个节点的左孩子和右孩子交换吗？

例如：

4 / \ 2 7

翻转以后：

4 / \ 7 2

但不只是根节点需要交换。

整棵树中，每一个节点都要执行同样的操作：

取出一个节点 ↓ 交换它的左孩子和右孩子 ↓ 继续处理后面的节点

所以这道题很适合继续使用前面学过的BFS + 队列。

整体思路：一个队列就够了

我一开始也想过：

要不要一个队列存左孩子，一个队列存右孩子？

后来发现完全没有必要。

因为我们真正处理的是：

当前这个节点本身。

每次从队列中拿出一个节点：

node=q.popleft()

然后交换：

node.left node.right

即可。

处理完当前节点后，再把它的孩子加入队列，继续处理。

所以一个队列就够了。

第一版思路

先处理特殊情况：

ifrootisNone:returnroot

如果根节点就是空的，直接返回。

然后创建队列：

q=deque([root])

这里的[root]表示：

创建一个只包含根节点的列表，再用它初始化队列。

也就是：

q=deque()q.append(root)

的简写。

每次从队列中取出当前节点

node=q.popleft()

然后先保存它原来的左右孩子：

node_left=node.left node_right=node.right

之后交换：

node.left=node_right node.right=node_left

这就是当前节点的翻转。

我踩的坑：把None直接加入了队列

我一开始直接写的是：

q.append(node_left)q.append(node_right)

没有判断左右孩子是否存在。

而 Python 的deque其实是允许放入：

None

的。

例如：

q.append(None)

这本身不会报错。

所以真正的问题是：

下一轮把None从队列中取出来以后，程序还会把它当成一个 TreeNode 使用。

例如：

node=q.popleft()

如果此时：

nodeisNone

后面再执行：

node.left

就会报错。

因为None根本没有：

.left.right

这些属性。

所以错误发生的流程其实是：

某个节点没有左孩子 ↓ node.left == None ↓ 把 None 加入队列 ↓ 下一轮 popleft() ↓ node = None ↓ 继续访问 node.left ↓ 报错

为什么交换时却不用判断 None？

这个地方我一开始有点疑惑。

既然：

node.left

可能是None，

那为什么交换的时候：

node.left=node_right node.right=node_left

不需要先判断？

因为：

把None赋值给一个节点的left或right是完全合法的。

比如：

node.left=None

只是表示：

当前节点没有左孩子。

这和访问：

None.left

是完全不同的事情。

可以区分成：

node.left = None

这是合法的：

给当前节点的 left 属性赋值为 None。

但是：

None.left

是不合法的：

试图从 None 这个对象中访问 left 属性。

所以：

赋值 None

没问题。

真正有问题的是：

把 None 当成 TreeNode 使用。

为什么None不需要加入队列？

这里我一开始有一个疑问：

deque明明可以存None，为什么这道题还要先判断左右孩子是否存在，再决定要不要入队？

后来想清楚以后发现，关键不在于：

None 能不能放进队列

而在于：

这个元素后面还需不需要继续处理

这道题中，队列的作用是：

保存接下来还需要进行 “左右孩子交换” 的节点。

每次：

node=q.popleft()

取出一个真实存在的节点，然后执行：

node.left,node.right=node.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.right=None

保存：

node_left=node.left node_right=node.right

得到：

node_left = 3 node_right = None

然后交换：

node.left=node_right node.right=node_left

就变成：

5 \ 3

也就是：

node.left=Nonenode.right=3

这完全合法。

所以交换的时候不需要判断：

None

是否存在。

为什么交换以后还是正确的？

这里还有一个容易绕的点。

我们是先保存：

node_left=node.left node_right=node.right

然后把原来的左右孩子加入队列：

ifnode_left:q.append(node_left)ifnode_right:q.append(node_right)

最后再交换：

node.left=node_right node.right=node_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 q=deque([root])whileq:node=q.popleft()node_left=node.left node_right=node.right# 只有真正存在的节点才需要继续处理ifnode_left:q.append(node_left)ifnode_right:q.append(node_right)# 交换当前节点的左右孩子node.left=node_right node.right=node_leftreturnroot

还可以进一步简化交换

Python 本身支持同时交换：

node.left,node.right=node.right,node.left

所以也可以写成：

fromcollectionsimportdequeclassSolution:definvertTree(self,root:Optional[TreeNode])->Optional[TreeNode]:ifrootisNone:returnroot q=deque([root])whileq:node=q.popleft()node.left,node.right=node.right,node.leftifnode.left:q.append(node.left)ifnode.right:q.append(node.right)returnroot

这里交换以后，再把新的左右孩子加入队列，也一样可以。

因为无论交换前还是交换后，最终都还是那两个孩子节点，只是左右位置发生了变化。

复杂度分析

设二叉树一共有n个节点。

每个节点都会：

进入队列一次 弹出一次 交换一次左右孩子

所以：

• 时间复杂度：O(n)

队列最坏情况下可能保存一整层的节点：

• 空间复杂度：O(n)

这道题我学到的点

1. 翻转二叉树的本质就是：

对每一个节点 交换 left 和 right

2. 一个队列就够了。队列只是负责保存：

接下来还有哪些节点需要处理

3. deque可以保存None，但这里没必要保存。因为None本身不需要继续处理。

4. 真正会报错的不是：

q.append(None)

而是之后：

node=Nonenode.left

因为None没有left属性。

5. 下面两件事要区分：

node.left=None

合法，表示没有左孩子。

但是：

None.left

非法，因为None不是TreeNode。

6. 队列里保存的是节点对象。

即使交换以后节点从左边跑到右边，它仍然是原来的那个TreeNode，所以后续依然可以正常处理。

总结

这道题用 BFS + 队列的思路其实很直接：

根节点入队 ↓ 弹出当前节点 ↓ 交换当前节点的左右孩子 ↓ 把存在的孩子加入队列 ↓ 继续处理下一个节点 ↓ 队列为空 ↓ 整棵树翻转完成

和之前几道 BFS 题相比，这道题更能说明：

BFS 不一定要一层一层做统计。

有时候我们只是借助队列，把整棵树中的每一个节点都访问一遍，然后对每个节点执行相同操作即可。