0199. 二叉树的右视图【中等】
1. 📝 题目描述
给定一个二叉树的 根节点 root,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。
示例 1:
txt
输入:root = [1,2,3,null,5,null,4]
输出:[1,3,4]1
2
2
- 解释:
示例 2:
txt
输入:root = [1,2,3,4,null,null,null,5]
输出:[1,3,4,5]1
2
2
- 解释:
示例 3:
txt
输入:root = [1,null,3]
输出:[1,3]1
2
2
示例 4:
txt
输入:root = []
输出:[]1
2
2
提示:
- 二叉树的节点个数的范围是
[0,100] -100 <= Node.val <= 100
2. 🎯 s.1 - BFS
c
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
int* rightSideView(struct TreeNode* root, int* returnSize) {
*returnSize = 0;
if (!root) return NULL;
int* res = (int*)malloc(sizeof(int) * 10000);
struct TreeNode** queue = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * 10000);
int front = 0, rear = 0;
queue[rear++] = root;
while (front < rear) {
int size = rear - front;
for (int i = 0; i < size; i++) {
struct TreeNode* node = queue[front++];
if (i == size - 1) res[(*returnSize)++] = node->val;
if (node->left) queue[rear++] = node->left;
if (node->right) queue[rear++] = node->right;
}
}
free(queue);
return res;
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
js
/**
* 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 res = []
const queue = [root]
while (queue.length) {
const size = queue.length
for (let i = 0; i < size; i++) {
const node = queue.shift()
if (i === size - 1) res.push(node.val)
if (node.left) queue.push(node.left)
if (node.right) queue.push(node.right)
}
}
return res
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
py
# 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 []
res = []
queue = deque([root])
while queue:
size = len(queue)
for i in range(size):
node = queue.popleft()
if i == size - 1:
res.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return res1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
- 时间复杂度:
,其中 是二叉树的节点数 - 空间复杂度:
,队列最多存储一层的节点
算法思路:
- BFS 层序遍历,每层取最后一个节点的值(即该层最右侧的节点)

