二叉树的右视图

题目要求：

给定一棵二叉树的层序数组表示，从右侧观察按层输出第一个可见节点值序列。

解题思路：

对二叉树进行层序遍历（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;
}

Leetcode 45.二叉树的右视图-原题链接

题目内容

给定一个二叉树的根节点 $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$