二叉树的右视图

怎样从“从右侧看树，每层最右可见节点 [1,3,4]。”推导出 二叉树 · 右视图，并证明每次状态变化都不会漏掉答案？

中心结论：BFS 每层取最后一个；DFS 先右后左，depth 首次记录。

从右边看一个树，输出看到的数字。注意有遮挡。

在本站主例中，从右侧看树，每层最右可见节点 [1,3,4]。

算法最终需要得到或观察：右视图序列 [1,3,4]。

从每个节点重新遍历子树会重复计算；递归让每棵子树只计算一次并向父节点返回摘要。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“递归回执树”，明确答案需要观察什么。
2. 2状态只维护 层序 queue+levelSize / DFS depth 首次。
3. 3转移每一步按照 BFS 每层取最后一个；DFS 先右后左，depth 首次记录。
4. 4收尾读取 右视图序列 [1,3,4]。，并复核边界与复杂度。

先用一句话定义递归函数返回什么，父节点才能正确合并。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：层序 queue+levelSize / DFS depth 首次。

这一题是按层序遍历的变种题。按照层序把每层的元素都遍历出来，然后依次取每一层的最右边的元素即可。用一个队列即可实现。 第 102 题和第 107 题都是按层序遍历的。

BFS 每层取最后一个；DFS 先右后左，depth 首次记录。

执行过程中持续维护：层序 queue+levelSize / DFS depth 首次。

正确性依赖以下不变量：右视图 = 每层从右侧可见的最右节点。；BFS 必须 levelSize 冻结本层再取最后一个。；DFS 必须先右后左，depth==len(ans) 时记录。

面试时可以压缩为：每层只取一个从右侧可见的节点。BFS 层序遍历 levelSize 冻结后取最后一个；DFS 先右后左，depth 首次到达即记录。时间 O(n)，BFS 空间 O(w)，DFS 空间 O(h)。

落到当前题，执行机制可以压缩为：BFS 每层取最后一个；DFS 先右后左，depth 首次记录。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入从右侧看树，每层最右可见节点 [1,3,4]。 因为：BFS 每层取最后一个；DFS 先右后左，depth 首次记录。
2. 2BFS 队列层序根入队。 因为：FIFO 保证同层顺序。
3. 3出队访问 2访问并把左右孩子入队。 因为：size 快照划分层界。
4. 4预测下一步先不要看下一帧——根据当前不变量,预测算法接下来会怎么动。 因为：主动预测会暴露你对不变量的真实理解,比被动看动画有效得多。
5. 5出队访问 3访问并把左右孩子入队。 因为：size 快照划分层界。
6. 6出队访问 5访问并把左右孩子入队。 因为：size 快照划分层界。
7. 7层序: [1] | [2,3] | [5,4]队列为空。 因为：O(n) BFS。
8. 8收尾与复杂度右视图序列 [1,3,4]。 因为：时间 O(n) · 空间 BFS O(w) · DFS O(h)，最坏均 O(n)。BFS 每层取最后一个；DFS 先右后左，depth 首次记录。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

// TreeNode define
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func rightSideView(root *TreeNode) []int {
	res := []int{}
	if root == nil {
		return res
	}
	queue := []*TreeNode{root}
	for len(queue) > 0 {
		n := len(queue)
		for i := 0; i < n; i++ {
			if queue[i].Left != nil {
				queue = append(queue, queue[i].Left)
			}
			if queue[i].Right != nil {
				queue = append(queue, queue[i].Right)
			}
		}
		res = append(res, queue[n-1].Val)
		queue = queue[n:]
	}
	return res
}

func main() {
    // 1. 主例
    //    输入：mode="level-order", values=[1,2,3,null,5,null,4]
    //    期望：右视图序列 [1,3,4]。
    //
    // 2. 失败 / 未命中
    //    检查：右视图不是沿 root.Right 一路向下。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC102 层序遍历：理解 levelSize；LC515 每层最大值：同样是逐层统计；左视图变体：DFS 先左后右 / BFS 取每层第一个
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意从右侧看树，每层最右可见节点 [1,3,4]。
2. 2重复从每个节点重新遍历子树会重复计算；递归让每棵子树只计算一次并向父节点返回摘要。
3. 3优化BFS 每层取最后一个；DFS 先右后左，depth 首次记录。
4. 4证明右视图 = 每层从右侧可见的最右节点。；BFS 必须 levelSize 冻结本层再取最后一个。；DFS 必须先右后左，depth==len(ans) 时记录。
5. 5复杂度时间 O(n)，空间 BFS O(w) · DFS O(h)，最坏均 O(n)