#P4062. 二叉树的右视图
-
ID: 2303
Tried: 61
Accepted: 22
Difficulty: 5
二叉树的右视图
题目内容
给定一个二叉树的根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，输出从右侧所能看到的节点值。
输入描述
- 第一行一个整数n，表示root的长度。
- 第二行为二叉树的序列化数组root，节点值之间用空格隔开，空节点用null表示。
输出描述
一行整数，表示从右侧所能看到的节点值。
样例1
输入
7
1 2 3 null 5 null 4
输出
1 3 4
说明
样例2
输入
8
1 2 3 4 null null null 5
输出
1 3 4 5
说明
样例3
输入
3
1 null 3
输出
1 3
提示
- 二叉树的节点个数的范围是 [0,100]
- −100<=Node.val<=100
二叉树的右视图
题目要求：
给定一棵二叉树的层序数组表示，从右侧观察按层输出第一个可见节点值序列。
解题思路：
对二叉树进行层序遍历（Breadth‑First Search）。每一层遍历时记录该层最后访问的节点值（即右侧可见节点）。遍历结束后按层输出这些值即可。
构建二叉树：输入给出层序数组（“null” 表示空），按照下标关系 left=2*i+1、right=2*i+2 将非空元素连接成 TreeNode。
复杂度分析
- 时间复杂度：
O(n)，n 为节点数，层序遍历访问每个节点一次。 - 空间复杂度：
O(n)，用于存储节点指针和队列。
代码实现
Python 代码
import sys
from collections import deque
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def build_tree(level_order):
if not level_order or level_order[0] == 'null':
return None
root = TreeNode(int(level_order[0]))
queue = [root]
i = 1
while i < len(level_order):
current = queue.pop(0)
# 构造左子节点
if i < len(level_order) and level_order[i] != 'null':
current.left = TreeNode(int(level_order[i]))
queue.append(current.left)
i += 1
# 构造右子节点
if i < len(level_order) and level_order[i] != 'null':
current.right = TreeNode(int(level_order[i]))
queue.append(current.right)
i += 1
return root
def right_side_view(root):
if not root:
return []
res = []
queue = deque([root])
while queue:
level_size = len(queue)
for i in range(level_size):
node = queue.popleft()
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
if i == level_size - 1:
res.append(node.val)
return res
if __name__ == "__main__":
n = int(sys.stdin.readline().strip())
arr = sys.stdin.readline().split()
root = build_tree(arr)
print(" ".join(map(str, right_side_view(root))))
Java 代码
import java.io.*;
import java.util.*;
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Main {
// 根据层次遍历构造二叉树
public static TreeNode buildTree(String[] tokens) {
if (tokens.length == 0 || tokens[0].equals("null"))
return null;
TreeNode root = new TreeNode(Integer.parseInt(tokens[0]));
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int i = 1;
while (i < tokens.length) {
TreeNode current = queue.poll();
// 构造左子节点
if (i < tokens.length && !tokens[i].equals("null")) {
current.left = new TreeNode(Integer.parseInt(tokens[i]));
queue.offer(current.left);
}
i++;
// 构造右子节点
if (i < tokens.length && !tokens[i].equals("null")) {
current.right = new TreeNode(Integer.parseInt(tokens[i]));
queue.offer(current.right);
}
i++;
}
return root;
}
public static 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(node.left != null) q.offer(node.left);
if(node.right != null) q.offer(node.right);
if(i == size - 1) ans.add(node.val);
}
}
return ans;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine().trim());
String[] arr = br.readLine().split(" ");
TreeNode root = buildTree(arr);
List<Integer> view = rightSideView(root);
for(int v : view) System.out.print(v + " ");
}
}
C++ 代码
#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
int val;
TreeNode *left, *right;
TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
};
// 根据层次遍历结果构造二叉树
TreeNode* buildTree(const vector<string>& tokens) {
if (tokens.empty() || tokens[0] == "null")
return nullptr;
TreeNode* root = new TreeNode(stoi(tokens[0]));
queue<TreeNode*> q;
q.push(root);
int i = 1;
while (i < tokens.size()) {
TreeNode* current = q.front();
q.pop();
// 构造左子节点
if (i < tokens.size() && tokens[i] != "null") {
current->left = new TreeNode(stoi(tokens[i]));
q.push(current->left);
}
i++;
// 构造右子节点
if (i < tokens.size() && tokens[i] != "null") {
current->right = new TreeNode(stoi(tokens[i]));
q.push(current->right);
}
i++;
}
return root;
}
vector<int> rightSideView(TreeNode* root) {
vector<int> ans;
if(!root) return ans;
queue<TreeNode*> q;
q.push(root);
while(!q.empty()) {
int sz = q.size();
for(int i = 0; i < sz; i++){
TreeNode* node = q.front(); q.pop();
if(node->left) q.push(node->left);
if(node->right) q.push(node->right);
if(i == sz - 1) ans.push_back(node->val);
}
}
return ans;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n; cin >> n;
vector<string> arr(n);
for(int i = 0; i < n; i++) cin >> arr[i];
TreeNode* root = buildTree(arr);
auto view = rightSideView(root);
for(int v : view) cout << v << " ";
return 0;
}