199. Binary Tree Right Side View
給定一個二叉樹的根節點，假設你站在它的右側，返回從上到下你能看到的節點值。
範例：
輸入：root = [1,2,3,null,5,null,4]
輸入：root = [1,2,3,null,5,null,4]
輸出：[1,3,4]
說明：
這個示例表示以下二叉樹：
1 / \ 2 3 \ \ 5 4
從右側看這棵樹，你能看到的節點依次是 1, 3, 4。
Python
from typing import List, Optional
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
from collections import deque
queue = deque([root])
right_side = []
while queue:
level_length = len(queue)
for i in range(level_length):
node = queue.popleft()
# If this is the last node in the current level, add it to the result
if i == level_length - 1:
right_side.append(node.val)
# Add child nodes in the queue
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return right_side
16.51MB, 33ms
C++
#include <vector>
#include <queue>
using namespace std;
class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
vector<int> right_side;
if (!root) {
return right_side;
}
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int level_length = q.size();
for (int i = 0; i < level_length; ++i) {
TreeNode* node = q.front();
q.pop();
// If this is the last node in the current level, add it to the result
if (i == level_length - 1) {
right_side.push_back(node->val);
}
// Add child nodes in the queue
if (node->left) {
q.push(node->left);
}
if (node->right) {
q.push(node->right);
}
}
}
return right_side;
}
};
14.44MB, 0ms
Javascript
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val);
* this.left = (left===undefined ? null : left);
* this.right = (right===undefined ? null : right);
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var rightSideView = function(root) {
if (!root) {
return [];
}
const queue = [];
const rightSide = [];
queue.push(root);
while (queue.length > 0) {
const levelLength = queue.length;
for (let i = 0; i < levelLength; i++) {
const node = queue.shift();
// If this is the last node in the current level, add it to the result
if (i === levelLength - 1) {
rightSide.push(node.val);
}
// Add child nodes in the queue
if (node.left) {
queue.push(node.left);
}
if (node.right) {
queue.push(node.right);
}
}
}
return rightSide;
};
51.6MB, 58ms
