199. 二叉树的右视图
题目描述
输入二叉树的根节点 root。假设你站在树的右边向左看，每一层只能看到最靠右的那个节点。
按从上到下的层次顺序，返回能看到的节点值。树为空时返回空数组。
树以层序数组表示，null 表示该位置没有节点。
示例 1
输入：root = [1,2,3,null,5,null,4] 输出：[1,3,4]
解释：三层最右侧的节点分别是 1、3、4。
示例 2
输入：root = [1,2,3,4,null,null,null,5] 输出：[1,3,4,5]
解释：第 3 层最右是 4；第 4 层只有 5，挂在 4 下面，也能看到。
示例 3
输入：root = [1,null,3] 输出：[1,3]
解释：第 2 层只有右孩子 3。
示例 4
输入：root = [] 输出：[]
解释：空树，返回空数组。
数据范围
- 节点数在
[0, 100]范围内。 -100 <= Node.val <= 100
解题思路：广度优先搜索（层序遍历）
按层从左到右遍历，记录每一层最后出队的节点。
为什么正确
同层队列顺序从左到右，最后一个节点就是该层最右节点。
复杂度分析
时间 O(n)，队列 O(w)，结果 O(h)。
易错点
右视图不是沿着 root.right 一直走；右子树缺层时左子树节点也可能可见。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
from collections import deque
class Solution:
def rightSideView(self, root):
if not root:
return []
queue = deque([root])
result = []
while queue:
size = len(queue)
for i in range(size):
node = queue.popleft()
if i == size - 1:
result.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return resultclass Solution {
public List<Integer> rightSideView(TreeNode root) {
if (root == null)
return new ArrayList<>();
Deque<TreeNode> queue = new ArrayDeque<>(List.of(root));
List<Integer> result = new ArrayList<>();
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (i == size - 1)
result.add(node.val);
if (node.left != null)
queue.offer(node.left);
if (node.right != null)
queue.offer(node.right);
}
}
return result;
}
}class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
if (!root)
return {};
queue<TreeNode*> q({root});
vector<int> result;
while (!q.empty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
TreeNode* node = q.front(); q.pop();
if (i == size - 1)
result.push_back(node->val);
if (node->left)
q.push(node->left);
if (node->right)
q.push(node->right);
}
}
return result;
}
};func rightSideView(root *TreeNode) []int {
if root == nil {
return []int{}
}
queue := []*TreeNode{root}
result := []int{}
for len(queue) > 0 {
size := len(queue)
for i := range size {
node := queue[0]; queue = queue[1:]
if i == size-1 {
result = append(result, node.Val)
}
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
}
}
return result
}var rightSideView = function(root) {
if (!root)
return [];
const queue = [root];
const result = [];
while (queue.length) {
const size = queue.length;
for (let i = 0; i < size; i++) {
const node = queue.shift();
if (i === size - 1)
result.push(node.val);
if (node.left)
queue.push(node.left);
if (node.right)
queue.push(node.right);
}
}
return result;
};function rightSideView(root: TreeNode | null): number[] {
if (!root)
return [];
const queue: TreeNode[] = [root];
const result: number[] = [];
while (queue.length) {
const size = queue.length;
for (let i = 0; i < size; i++) {
const node = queue.shift()!;
if (i === size - 1)
result.push(node.val);
if (node.left)
queue.push(node.left);
if (node.right)
queue.push(node.right);
}
}
return result;
};其他解法
BFS 逐层取最后一个结点，空间取决于最宽的一层；DFS 先走右子树，用“每层第一次访问”来确定最右结点，空间取决于树高。
解法 2：深度优先搜索（先右后左） 时间 O(n)，空间 O(h)
按“根 → 右子树 → 左子树”的顺序递归，同时传入当前深度 depth。每一层最先访问到的结点就是该层最右侧的结点。当 depth 等于结果数组长度时，说明这是该层第一次被访问，把结点值加入结果。
代码更短，空间只跟树高有关。但树退化成链时递归很深；“先右后左”的顺序也不如层序遍历直观。
from typing import List, Optional
class Solution:
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
res = []
def dfs(node, depth):
if node is None:
return
if depth == len(res):
res.append(node.val)
dfs(node.right, depth + 1)
dfs(node.left, depth + 1)
dfs(root, 0)
return resclass Solution {
private List<Integer> res;
public List<Integer> rightSideView(TreeNode root) {
res = new ArrayList<>();
dfs(root, 0);
return res;
}
private void dfs(TreeNode node, int depth) {
if (node == null) return;
if (depth == res.size()) res.add(node.val);
dfs(node.right, depth + 1);
dfs(node.left, depth + 1);
}
}class Solution {
vector<int> res;
void dfs(TreeNode* node, int depth) {
if (!node) return;
if (depth == (int)res.size()) res.push_back(node->val);
dfs(node->right, depth + 1);
dfs(node->left, depth + 1);
}
public:
vector<int> rightSideView(TreeNode* root) {
res.clear();
dfs(root, 0);
return res;
}
};func rightSideView(root *TreeNode) []int {
res := []int{}
var dfs func(node *TreeNode, depth int)
dfs = func(node *TreeNode, depth int) {
if node == nil {
return
}
if depth == len(res) {
res = append(res, node.Val)
}
dfs(node.Right, depth+1)
dfs(node.Left, depth+1)
}
dfs(root, 0)
return res
}var rightSideView = function(root) {
const res = [];
const dfs = (node, depth) => {
if (!node) return;
if (depth === res.length) res.push(node.val);
dfs(node.right, depth + 1);
dfs(node.left, depth + 1);
};
dfs(root, 0);
return res;
};function rightSideView(root: TreeNode | null): number[] {
const res: number[] = [];
const dfs = (node: TreeNode | null, depth: number): void => {
if (!node) return;
if (depth === res.length) res.push(node.val);
dfs(node.right, depth + 1);
dfs(node.left, depth + 1);
};
dfs(root, 0);
return res;
};