LeetCode 199: Binary Tree Right Side View (Level-Order Last Node Capture)
LeetCode 199Binary TreeBFSQueueToday we solve LeetCode 199 - Binary Tree Right Side View. The key is to process level by level and keep the last node seen in each level.
Source: https://leetcode.com/problems/binary-tree-right-side-view/
English
Problem Summary
Given the root of a binary tree, return the values of the nodes you can see when looking from the right side, from top to bottom.
Key Insight
Nodes visible from the right correspond to the last node in each depth level when traversing level by level (BFS).
Optimal Algorithm (BFS by Levels)
1) If root is null, return empty list.
2) Push root into a queue.
3) For each level, process exactly size nodes.
4) When processing index i == size - 1, append that node's value to answer.
5) Push left and right children for next level.
Complexity Analysis
Time: O(n) — every node visited once.
Space: O(w) — queue stores up to tree width.
Common Pitfalls
- Not freezing current level size before loop, which mixes levels.
- Appending first node instead of last node at each level.
- Forgetting root null check.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> ans = new ArrayList<>();
if (root == null) return ans;
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
TreeNode node = q.poll();
if (i == size - 1) ans.add(node.val);
if (node.left != null) q.offer(node.left);
if (node.right != null) q.offer(node.right);
}
}
return ans;
}
}func rightSideView(root *TreeNode) []int {
ans := []int{}
if root == nil {
return ans
}
q := []*TreeNode{root}
for len(q) > 0 {
size := len(q)
for i := 0; i < size; i++ {
node := q[0]
q = q[1:]
if i == size-1 {
ans = append(ans, node.Val)
}
if node.Left != nil {
q = append(q, node.Left)
}
if node.Right != nil {
q = append(q, node.Right)
}
}
}
return ans
}class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
vector<int> ans;
if (!root) return ans;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
TreeNode* node = q.front();
q.pop();
if (i == size - 1) ans.push_back(node->val);
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
}
return ans;
}
};from collections import deque
class Solution:
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
ans = []
if not root:
return ans
q = deque([root])
while q:
size = len(q)
for i in range(size):
node = q.popleft()
if i == size - 1:
ans.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return ans/**
* @param {TreeNode} root
* @return {number[]}
*/
var rightSideView = function(root) {
const ans = [];
if (!root) return ans;
const q = [root];
while (q.length > 0) {
const size = q.length;
for (let i = 0; i < size; i++) {
const node = q.shift();
if (i === size - 1) ans.push(node.val);
if (node.left) q.push(node.left);
if (node.right) q.push(node.right);
}
}
return ans;
};中文
题目概述
给定二叉树根节点 root，返回从右侧观察时能看到的节点值，按从上到下顺序输出。
核心思路
右视图本质上就是每一层最右边的节点。用层序遍历时，每层最后弹出的节点就是答案。
最优算法（按层 BFS）
1）空树直接返回空数组。
2）根节点入队。
3）每轮先记录当前层节点数 size。
4）遍历该层时，当下标 i == size - 1，把节点值加入结果。
5）把左右孩子加入队列，进入下一层。
复杂度分析
时间复杂度：O(n)，每个节点访问一次。
空间复杂度：O(w)，队列最多存一层宽度。
常见陷阱
- 没有先固定当前层 size，导致层边界混乱。
- 误把每层第一个节点加入答案。
- 忘记处理空树。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> ans = new ArrayList<>();
if (root == null) return ans;
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
TreeNode node = q.poll();
if (i == size - 1) ans.add(node.val);
if (node.left != null) q.offer(node.left);
if (node.right != null) q.offer(node.right);
}
}
return ans;
}
}func rightSideView(root *TreeNode) []int {
ans := []int{}
if root == nil {
return ans
}
q := []*TreeNode{root}
for len(q) > 0 {
size := len(q)
for i := 0; i < size; i++ {
node := q[0]
q = q[1:]
if i == size-1 {
ans = append(ans, node.Val)
}
if node.Left != nil {
q = append(q, node.Left)
}
if node.Right != nil {
q = append(q, node.Right)
}
}
}
return ans
}class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
vector<int> ans;
if (!root) return ans;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
TreeNode* node = q.front();
q.pop();
if (i == size - 1) ans.push_back(node->val);
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
}
return ans;
}
};from collections import deque
class Solution:
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
ans = []
if not root:
return ans
q = deque([root])
while q:
size = len(q)
for i in range(size):
node = q.popleft()
if i == size - 1:
ans.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return ans/**
* @param {TreeNode} root
* @return {number[]}
*/
var rightSideView = function(root) {
const ans = [];
if (!root) return ans;
const q = [root];
while (q.length > 0) {
const size = q.length;
for (let i = 0; i < size; i++) {
const node = q.shift();
if (i === size - 1) ans.push(node.val);
if (node.left) q.push(node.left);
if (node.right) q.push(node.right);
}
}
return ans;
};
Comments