Medium

题目描述

给定一棵二叉树的根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例 1：

输入: root = [1,2,3,null,5,null,4]
输出: [1,3,4]

示例 2：

输入: root = [1,2,3,4,null,null,null,5]
输出: [1,3,4,5]

示例 3：

输入: root = [1,null,3]
输出: [1,3]

示例 4：

输入: root = []
输出: []

提示：

  • 二叉树的节点个数的范围是 [0,100]
  • -100 <= Node.val <= 100

解题思路

解题思路

这道题要求我们获得二叉树的右视图，即从右侧看到的节点值。关键在于理解：对于每一层，我们只能看到最右边的节点。

方法一：层序遍历（BFS）- 推荐

使用广度优先搜索，按层遍历二叉树。对于每一层，记录最后一个（最右边的）节点值。这是最直观的解法：

  1. 使用队列进行层序遍历
  2. 对每一层，遍历完所有节点后，将最后一个节点值加入结果

方法二：深度优先搜索（DFS）

利用"先访问右子树，再访问左子树"的策略。对于每个深度，第一次访问到的节点就是该层最右边的节点：

  1. 递归时先遍历右子树，再遍历左子树
  2. 使用深度标记，每个深度第一次访问的节点就是答案

方法三：反向层序遍历

从右到左进行层序遍历，每层的第一个节点就是右视图中的节点。

BFS方法最容易理解且实现简洁，是推荐解法。

代码实现

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> result;
        if (!root) return result;
        
        queue<TreeNode*> q;
        q.push(root);
        
        while (!q.empty()) {
            int levelSize = q.size();
            
            for (int i = 0; i < levelSize; i++) {
                TreeNode* node = q.front();
                q.pop();
                
                // 如果是当前层的最后一个节点，加入结果
                if (i == levelSize - 1) {
                    result.push_back(node->val);
                }
                
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
        }
        
        return result;
    }
};

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        
        result = []
        queue = deque([root])
        
        while queue:
            level_size = len(queue)
            
            for i in range(level_size):
                node = queue.popleft()
                
                # 如果是当前层的最后一个节点，加入结果
                if i == level_size - 1:
                    result.append(node.val)
                
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        
        return result

public class Solution {
    public IList<int> RightSideView(TreeNode root) {
        IList<int> result = new List<int>();
        if (root == null) return result;
        
        Queue<TreeNode> queue = new Queue<TreeNode>();
        queue.Enqueue(root);
        
        while (queue.Count > 0) {
            int levelSize = queue.Count;
            
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.Dequeue();
                
                // 如果是当前层的最后一个节点，加入结果
                if (i == levelSize - 1) {
                    result.Add(node.val);
                }
                
                if (node.left != null) queue.Enqueue(node.left);
                if (node.right != null) queue.Enqueue(node.right);
            }
        }
        
        return result;
    }
}

var rightSideView = function(root) {
    if (!root) return [];
    
    const result = [];
    const queue = [root];
    
    while (queue.length > 0) {
        const levelSize = queue.length;
        
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();
            
            if (i === levelSize - 1) {
                result.push(node.val);
            }
            
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型BFS层序遍历DFS深度优先
时间复杂度O(n)O(n)
空间复杂度O(w)O(h)

其中 n 是二叉树的节点数，w 是二叉树的最大宽度，h 是二叉树的高度。

  • BFS的空间复杂度取决于队列中同时存储的最大节点数（即树的最大宽度）
  • DFS的空间复杂度取决于递归调用栈的深度（即树的高度）

相关题目