二叉树右视图问题解析：BFS与DFS算法实现与优化

1. 问题背景与核心思路

二叉树的右视图问题在算法面试中属于高频考点，尤其出现在力扣（LeetCode）的热门100题榜单中。这个问题的本质是要求我们从二叉树的右侧观察时能看到的节点序列。想象你站在一棵二叉树的右侧，从顶部到底部，每一层最右边的节点就是你能看到的"右视图"。

我第一次遇到这个问题是在准备某大厂面试时，当时被要求15分钟内白板编码。实际解决过程中发现，看似简单的题目藏着不少考察点：层序遍历的变种、空间复杂度的优化、以及边界条件的处理。下面我会结合多次刷题和面试官反馈的经验，拆解这个问题的解决思路和优化技巧。

2. 基础解法：层序遍历法

2.1 标准BFS实现

最直观的解法是使用广度优先搜索（BFS）进行层序遍历，记录每一层的最后一个节点：

python复制from collections import deque

def rightSideView(root):
    if not root:
        return []
    
    queue = deque([root])
    result = []
    
    while queue:
        level_size = len(queue)
        for i in range(level_size):
            node = queue.popleft()
            if i == level_size - 1:  # 只记录每层最后一个节点
                result.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    return result

关键点：在每层遍历时，通过level_size控制只处理当前层的节点，确保i == level_size - 1时捕获的就是最右侧节点。

2.2 时间复杂度分析

• 时间复杂度：O(N)，每个节点被访问一次
• 空间复杂度：O(D)，D为树的直径，最坏情况下是O(N)

3. 优化解法：DFS优先遍历

3.1 改进的深度优先搜索

虽然BFS直观，但DFS可以在特定情况下优化空间复杂度：

python复制def rightSideView(root):
    result = []
    
    def dfs(node, depth):
        if not node:
            return
        
        if depth == len(result):  # 当前深度首次访问
            result.append(node.val)
        
        dfs(node.right, depth + 1)  # 优先访问右子树
        dfs(node.left, depth + 1)
    
    dfs(root, 0)
    return result

技巧：通过优先遍历右子树的策略，确保每层第一个访问到的节点就是右视图节点。depth参数与result长度的比较是关键判断条件。

3.2 两种方法的对比

4. 边界条件与特殊测试用例

4.1 常见边界情况

1. 空树：root = None → 应返回[]
2. 单节点树：[1] → 应返回[1]
3. 完全左斜树：[1,2,null,3,null] → 应返回[1,2,3]
4. 完全右斜树：[1,null,2,null,3] → 应返回[1,2,3]

4.2 易错点警示

• 忘记处理空树情况导致NullPointerException
• BFS中未正确维护level_size导致跨层混合
• DFS中depth参数传递错误（应传depth+1而非depth++）
• 混淆节点值追加顺序（右视图是先右后左）

5. 实际面试中的变种问题

5.1 左视图问题

只需调整遍历顺序即可解决：

python复制# BFS版：改为记录每层第一个节点
if i == 0:
    result.append(node.val)

# DFS版：改为先遍历左子树
dfs(node.left, depth + 1)
dfs(node.right, depth + 1)

5.2 顶视图问题

需要结合深度和水平位置信息：

python复制from collections import defaultdict

def topView(root):
    pos_dict = defaultdict(list)
    min_pos = max_pos = 0
    
    def dfs(node, pos, depth):
        nonlocal min_pos, max_pos
        if not node:
            return
        
        min_pos = min(min_pos, pos)
        max_pos = max(max_pos, pos)
        
        if pos not in pos_dict or depth < pos_dict[pos][1]:
            pos_dict[pos] = (node.val, depth)
        
        dfs(node.left, pos - 1, depth + 1)
        dfs(node.right, pos + 1, depth + 1)
    
    dfs(root, 0, 0)
    return [pos_dict[i][0] for i in range(min_pos, max_pos + 1)]

6. 性能优化实战技巧

6.1 BFS的空间优化

当处理超大树时，可以改用两个队列交替使用：

python复制def rightSideView(root):
    if not root:
        return []
    
    current_level = [root]
    result = []
    
    while current_level:
        result.append(current_level[-1].val)  # 直接取最后一个元素
        next_level = []
        for node in current_level:
            if node.left:
                next_level.append(node.left)
            if node.right:
                next_level.append(node.right)
        current_level = next_level
    return result

6.2 迭代式DFS实现

避免递归栈溢出的迭代方案：

python复制def rightSideView(root):
    result = []
    stack = [(root, 0)]
    
    while stack:
        node, depth = stack.pop()
        if not node:
            continue
            
        if depth == len(result):
            result.append(node.val)
        
        # 注意入栈顺序：先左后右，出栈时就是先右后左
        stack.append((node.left, depth + 1))
        stack.append((node.right, depth + 1))
    
    return result

7. 同类问题扩展训练

为了巩固这类问题的解决能力，推荐练习以下力扣题目：

1. 二叉树的层序遍历（#102）
2. 二叉树的锯齿形层序遍历（#103）
3. 二叉树的最小深度（#111）
4. 二叉树的垂序遍历（#987）
5. 二叉树的边界（#545）

我在实际刷题中发现，掌握右视图问题的解法后，这些相关题目都能迎刃而解。特别是对于#102和#103，只需要调整结果收集策略即可。建议先用BFS实现基础解法，再用DFS尝试优化，最后处理各种边界条件。