二叉树的右视图：BFS与DFS两种解法详解

1. 这道题到底在问什么：从“站在右边看”到树的层级透视图

1.1 题目原意拆解：右视图不是“右子树视图”

LeetCode hot100 里二叉树题目不少，199题“二叉树的右视图”是其中辨识度很高的一道。简单说，题目给你一棵二叉树，要你想象自己站在树的右侧，从顶部到底部依次返回“每层你能看到的最右边的那个节点值”。

这里最关键的一个认知误区，也是这道题真正的考点：右视图不是把右子树上的节点一路收集起来。很多人第一眼看到“右视图”三个字，下意识以为答案就是把右分支全部走一遍，比如根节点有右孩子就一直往右下走，没右孩子了就往右下下走，认为收集到的路径就是答案。这个思路错得离谱，而且错得很有代表性。

举个最典型的反例：一棵树只有一个根节点和一条极深的左子树，完全没有右子树。站在右侧看，你看到的节点不是“根节点就结束了”，而是沿着左子树一路深入，每一层都能看到那个最靠右的节点。也就是说，那棵看似“藏在左边”的子树，在某一层如果没有其他节点挡在前面，它就是你视野里的最右节点。所以右视图的本质是每层所有节点中位置最靠右的那个，而不是“右子树的节点”。

1.2 为什么“看不见”的节点不重要：问题的核心是层次最右

把二叉树想成一个二维结构：每一层是一排节点，站在最右侧，每一排你能看到的，是这一排里最后一个节点。至于这排的右边还有没有别的节点，或者这一排的节点是不是右子树里的，统统不重要。你需要关注的是“层”，而不是“路径”。

这个“层”的概念，直接决定了两个主流的解题方向：

• 用层序遍历（BFS），一行一行地扫，每到一层的末尾，记录一下当前层最后弹出的节点。
• 用深度优先遍历（DFS），优先访问右子树，保证每层第一个被访问到的节点，就是从右边能看见的节点。

理解了“层”之后，这道题你已经会了一半。剩下的一半是代码层面的事情。

1.3 用超市货架理解层与剪影：不需要知道货架内部是什么

我经常拿超市货架来打比方。你站在一排货架的右侧走廊，目光顺着货架方向扫过去，你能看见的是这一排货架最右边的一件商品。下一排货架可能比这一排深，也可能比这一排浅，但你永远只关心“这一排最右的那个商品”是什么。在这个例子中，货架就是树的层级，货架上摆放的商品就是这一层的节点，你作为观察者，站的位置决定了你只取每层最右的那一个值。

这听起来简单，但真正在写二叉树程序时，“层”的边界常常被忽略，尤其是当一个节点只有左孩子、而它的兄弟节点位置为空的时候，很多人就开始含糊了。199题恰好用最直接的方式，逼着你去面对“层”的边界问题。

2. 解法一：层序遍历（BFS）——最直观、最少出错的思路

2.1 BFS为什么天然匹配“每层的最右侧”

如果你想按“层”来拿最右节点，最简单的做法就是用队列做层序遍历，也就是广度优先遍历。BFS的特性就是严格按照树的深度，从上到下、从左到右地把所有节点“扫”一遍。既然是按层扫，那么每一层什么时候算结束，就是一个可以被精确控制的事件。

在二叉树的右视图这道题里，你只需要做一件事：在每一层的节点全部从队列中弹出之前，把这一层最后一个弹出的节点值记录下来。这个“最后一个弹出的节点”，就是站在右侧能看到的那一个。

为什么BFS版本不容易出错？因为它不需要判断“当前节点是从右边还是左边过来的”，也不需要记录复杂的深度信息。它只是朴素地把树拆成一排一排的节点，然后告诉你每一排最右边的值是什么。逻辑非常线性，几乎没有给“灵机一动”的错误留下空间。

2.2 代码实现：用 size 固定当前层的边界

BFS 层序遍历实现右视图，最常见的写法是“size 法”。核心逻辑是：在每一轮循环开始时，先记下当前队列的长度，这个长度就是当前层的节点总数。接下来只处理这个数量的节点，每处理一个就把它左孩子右孩子入队，处理到当前层最后一个节点时，把这个节点的值加入答案。

from collections import deque class Solution: def rightSideView(self, root: Optional[TreeNode]) -> List[int]: if not root: return [] res = [] q = deque([root]) while q: level_size = len(q) for i in range(level_size): node = q.popleft() if i == level_size - 1: res.append(node.val) if node.left: q.append(node.left) if node.right: q.append(node.right) return res

为什么要用level_size = len(q)先把长度存下来？因为你在for循环体内部还会执行q.append，如果直接在for i in range(len(q))里取长度，这个长度会在循环过程中不断变化，导致当前层还没处理完，就已经混入了下一层的节点。这是层序遍历里最经典的坑，前面提到的“写二叉树程序时为什么总是报运行时错误”很多就是由这类问题引发的。先把level_size固定住，循环的次数就等于当前层节点数，干净利落。

2.3 其他流派：双队列法和哨兵法

面试官有时会追问：如果不用len(q)怎么知道一层结束了？这时候你可以说出两种替代写法作为知识储备。

第一种是双队列法。准备两个队列，current和next。从current里不断弹出节点，把子节点放进next，当current空了，说明这一层结束了，此刻next里装的就是下一层的全部节点，交换两个队列继续下一轮。这个写法稍微繁琐，但“当前层清空即一层结束”的概念更古朴。

第二种是哨兵法。在队列里塞入一个特殊标记值，例如None，作为层的分隔符。每次弹出None时，说明当前层遍历完毕。这种写法写起来短，但要注意None不能被当成真正的节点去访问属性，否则直接空指针报错。相比这两者，size法在代码可读性和易维护性上都有明显优势，所以我个人建议无论面试还是平时刷题，主用size法就够了，其他写法知道原理即可。

2.4 复杂度分析与边界情况

BFS版本的时间复杂度是 O(n)，因为每个节点恰好入队一次、出队一次。空间复杂度是 O(n)，最坏情况出现在完全二叉树的最后一层，队列里需要同时容纳约 n/2 个节点。这个空间占用对于二叉树题目来说是可接受的，但如果面试官对空间有更高要求，你可以顺势引出DFS版本。

边界情况主要就三件事：

• 空树：直接返回空列表，if not root这一行就能挡住。
• 只有一个根节点：返回包含根节点值的单元素列表。
• 左子树特别深、右子树很浅：右视图的后半部分来自左子树深处的节点。这时BFS版本不会错，因为它每一层都取“最后一个节点”，跟这个节点属于左子树还是右子树没有任何关系。这道题的所有边界情况里，就数这个最值得自己画图验证。

3. 解法二：DFS右路优先——空间复杂度更优的递归思路

3.1 递归遍历顺序的巧妙转变：先走右子树，每层第一个访问的节点就是答案

如果你不想用队列，或者面试官希望你展示递归功底，那么DFS版本同样优雅。这个版本的思路是一个很有技巧性的转变：既然我们要的是“每层最右侧的节点”，那就在递归时永远优先访问右子树，再访问左子树。这样一来，对于每一层来说，第一个被访问到的节点，必然是该层最右侧的节点。

为什么？想象一下递归的访问顺序：从根开始，先下到右子树的最深处，把每一层的最右节点访问完，再绕回左子树。当递归第一次进入某一深度时，这个深度的res里还没有值，说明还没有任何节点在这一层被记录过，那么当前这个节点一定是这一层最靠右的；如果res在这一层已经有值了，说明更右边的节点早就被记下来了，当前节点不需要再管。

3.2 代码实现：递归版

用一个辅助函数dfs(node, depth)，depth表示当前节点所在的层数。每次进入一个新的深度，如果depth == len(res)，说明这个深度第一次被访问到，直接把当前节点加入结果。

class Solution: def rightSideView(self, root: Optional[TreeNode]) -> List[int]: res = [] def dfs(node, depth): if not node: return if depth == len(res): res.append(node.val) dfs(node.right, depth + 1) dfs(node.left, depth + 1) dfs(root, 0) return res

注意观察递归顺序：先递归node.right，再递归node.left。如果把这两行调换顺序，代码就不再是右视图，而变成了某种“左视图”。所以这行顺序就是整个DFS解法的灵魂。很多人在面试时一紧张就会写成先左后右，结果答案莫名其妙变成了左视图，这个细节一定要死记。

3.3 迭代版：用栈模拟预处理顺序

递归虽然简洁，但递归深度在极端情况下可能爆栈。如果你想在空间上做得更可控，可以把递归改成显式栈。这里有个很容易踩的坑：因为栈是后进先出，你想要“先访问右子树”，入栈时就要先压左子树，再压右子树，这样弹出时右子树才会先被处理，顺序才能和递归保持一致。

class Solution: def rightSideView(self, root: Optional[TreeNode]) -> List[int]: res = [] stack = [(root, 0)] while stack: node, depth = stack.pop() if not node: continue if depth == len(res): res.append(node.val) stack.append((node.left, depth + 1)) stack.append((node.right, depth + 1)) return res

这里栈里保存的是(node, depth)二元组，当弹出栈顶节点时，如果当前深度等于len(res)，说明这个深度还没有被记录过，记录下来即可。在整个过程中，我们并不需要维护复杂的“当前层宽度”，因为深度信息已经足够抽象了，这也是DFS版本代码往往比BFS版本更短的原因。

3.4 两种解法的取舍：面试时怎么选

我一个比较实用的建议是：两道题都写熟，面试时优先展示你觉得更能讲清楚的解法。但如果你只想背一个，我建议优先背BFS版本，因为它的思路更贴近题目本身（“层”的概念），面试官追问“边界情况怎么处理”的时候，BFS版本的变量在哪儿、逻辑在哪儿都比较清晰，容易展开讲。

下面是两种解法的对比，供你复习时参考：

至于怎么选，我个人的习惯是：如果这棵树可能非常深，比如退化成一条链表，那么BFS永远安全，而递归DFS可能在到达第1000层时触发语言默认的递归深度限制。所以面试时如果面试官问“这棵树可能有一万层”，你就该意识到该用BFS或DFS迭代版本。

4. 写二叉树程序时为什么总是报运行时错误：199题现场踩坑复盘

4.1 最常见的运行时错误：空指针解引用

网上搜“写二叉树程序时为什么总是报运行时错误”，十个有八个都栽在空指针上。二叉树程序到处是node.left、node.right、node.val，一旦某个节点是None，你却继续访问它的属性，运行时立刻抛异常。

在199题里，这个坑最容易出现在DFS递归版本中。比如有的人写出这样的代码：

def dfs(node, depth): if depth == len(res): res.append(node.val) dfs(node.right, depth + 1) dfs(node.left, depth + 1)

没有if not node这个递归出口。当递归走到叶节点的下一层时，node已经变成了None，下一层递归调用函数体里的node.val自然报AttributeError: 'NoneType' object has no attribute 'val'。这样的报错信息在LeetCode上见得特别多。

解决办法很固定：递归函数的第一句话，永远是空的判断。先if not node: return，再做任何其他操作。记住这个顺序，二叉树递归题的运行时错误能减少八成。

4.2 递归深度爆栈：树退化成链表时的问题

第二个高频错误是栈溢出。二叉树在题目里往往看上去很“丰满”，但测试用例里完全可能包含极端情况：一棵退化成了链表的树，深度等于节点数。如果树有一万个节点，递归深度就有一万层，而Python默认的递归深度限制大约在1000层左右，超了就是RecursionError。

这个坑在199题的DFS递归写法里很容易出现。解决办法有三个：

• 改用BFS解法，不使用调用栈，从根本上避开递归深度问题。
• 改用DFS迭代栈，显式控制栈空间。
• 如果必须用递归，在代码开头调用sys.setrecursionlimit(10000)，但这只是把限制调大，不是根治。

我建议优先选择第一种或第二种。因为这类题考的往往是遍历逻辑，而不是你调高递归限制的熟练度。

4.3 层序遍历中“长度动态变化”的隐蔽索引问题

还有一个很隐蔽的BFS错误，前面提过，但值得单独复盘。有人会写出这样的代码：

while q: for i in range(len(q)): node = q.popleft() # ... q.append(node.left) q.append(node.right)

表面上看for i in range(len(q))是正常的，但实际上len(q)在循环过程中是动态变化的。每执行一次q.popleft()，队列长度减一；每执行一次q.append(...)，队列长度又增加。结果就是这个for循环根本不会按照“当前层节点数”来执行，它可能只处理了当前层的一部分节点，也可能把下一层的节点也混进来处理了，最终导致res里记录的“最右节点”并不是真正的最右节点。

正确写法就是前面代码里的level_size = len(q)。把长度先固化下来，循环次数就等于进入循环那一刻队列的长度，也就是当前层的真实节点数。这个问题的排查其实很简单——用一个小例子在纸上画一下队列的变化，比盯着代码看半天有效得多。

4.4 复盘后的通用防错清单

把上面三个坑总结成一份清单，我写二叉树代码时会按顺序过一遍：

• 入口处先判空，root为空直接返回。
• 递归函数的第一句必须是空节点判断，绝不允许在None上访问属性。
• BFS层序遍历时，先level_size = len(q)固定当前层宽度，不要在循环里直接用len(q)。
• DFS版本中的递归顺序要想清楚：右视图是先右后左，左视图是先左后右。
• 深度从0开始还是从1开始，前后要保持一致，测试用例至少跑一个“根节点只有左子树的树”。

每次做完一道二叉树题，拿这个清单对着代码过一遍，基本能杜绝大多数运行时错误。

5. 一道题带出的一串变体：左视图、之字形与垂直遍历

5.1 左视图怎么改：一行代码的事

做完了右视图，左视图就非常简单了。如果你用的是BFS解法，只需要把if i == level_size - 1:改成if i == 0:，意思是记录当前层的第一个节点，也就是站在左侧能看到的最左节点。如果你用的是DFS解法，把递归顺序改回“先左后右”，即先递归node.left再递归node.right，这样每一层第一个被访问到的节点就是最左节点。

这两个改法我在面试时被问过很多次，每次讲完“右视图”之后，面试官会顺嘴问一句“那左视图呢？”。这其实是在考察你是否真的理解了代码里的每一行，而不是背模板。所以建议你写右视图时，顺手在草稿纸上把左视图的版本也写一遍，加深记忆。

5.2 之字形遍历和右视图的组合题

二叉树的热门题里，之字形遍历（也叫锯齿形遍历）经常和右视图放在一起讨论。之字形遍历要求奇数层从左往右访问，偶数层从右往左访问。如果这时候题目变成“返回之字形遍历中的每一层最右节点”，需要小心一个点：在偶数层，访问方向变成了从右往左，那么这一层的“最右节点”其实是第一个被访问到的节点。

这个题目一旦组合起来，很多人的第一反应是乱了。正确做法还是回到定义：右视图就是每一层最右边的节点。不管遍历方向是从左往右还是从右往左，你只需要确定“这一层节点里，最右的那个是谁”。BFS解法在这种情况下依然可靠，因为你是先把整层节点全部拿到，再取最右的那个，而不是在遍历过程中顺便记录。

5.3 进阶延伸：垂直遍历与列优先思维

如果你想把199题理解得更透，可以去看看二叉树垂直遍历（Vertical Order Traversal）。那道题需要给每个节点记录列号，根节点为0列，左孩子列号减一，右孩子列号加一，最后按列分组输出。其实右视图和垂直遍历有一种奇妙的联系：一棵二叉树的右视图，某种意义上就是从正右侧看过去那些“列号最大的节点”的剪影。当你建立起“层”和“列”的坐标感之后，你会发现二叉树题目从抽象的空间想象变成了坐标计算，难度会下降一个档次。

当然这个延伸属于进阶内容，如果你是在准备面试的早期阶段，先把右视图的两种解法吃透更重要。等199题完全通关，再花时间去啃垂直遍历不迟。

5.4 从“hot100题”谈这类题的刷题策略

hot100 之所以叫 hot100，是因为这些题目浓缩了大多数公司面试中最高频的考点和套路。199题在 hot100 的二叉树分类里位置不算靠前，但它很典型：考察遍历顺序、层级概念、边界处理，这几个要素组合在一起，几乎是一张二叉树入门的试金石。

我的建议是，刷这类题时不要追求“只写对一次”，而是追求“能给别人讲明白”。每做完一题，合上代码，自己口述一遍思路，说清楚为什么取这个节点、为什么用这个遍历顺序、边界条件有哪些。如果你能在5分钟内讲清楚199题的两种解法，那你的hot100刷题质量会明显提升。真正面试的时候，你也不大可能一字不差地把代码背出来，但你能把思路讲清楚，面试官就很满意了。

写到这里，我再分享一个自己的小习惯。我最初做199题的时候，先写的是“一路向右”的错误版本，提交后没通过，当时我觉得题目很冤枉人，明明叫右视图。后来我画了一棵“只有左子树、没有右子树”的树，看着那棵树我才彻底想明白：右视图不是“右子树的视图”。从那以后，我刷树相关的题，第一件事就是画一棵不对称的树，比如根节点只有一个左孩子，把所有候选解法在这棵树上先跑一遍，能挡住大量低级错误。这个习惯后来帮我避开过不少运行时错误和逻辑错误，你也值得试试。