LeetCode 第199题：二叉树的右视图

题目描述

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

难度

中等

题目链接

点击在LeetCode中查看题目

示例

示例 1:

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

示例 2:

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

示例 3:

输入: []
输出: []

提示

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

解题思路

方法一：广度优先搜索（BFS）

使用BFS遍历二叉树，对于每一层，我们只需要记录最后一个节点的值。

关键点：

1. 使用队列存储每一层的节点
2. 对于每一层，记录最后一个节点的值
3. 将下一层的节点加入队列

时间复杂度：O(n)，其中n是二叉树的节点数 空间复杂度：O(w)，其中w是二叉树的最大宽度

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

使用DFS遍历二叉树，记录每一层最右边的节点。

关键点：

1. 使用递归进行DFS遍历
2. 记录当前深度，只在第一次到达该深度时记录节点值
3. 优先遍历右子树，再遍历左子树

时间复杂度：O(n)，其中n是二叉树的节点数 空间复杂度：O(h)，其中h是二叉树的高度

方法三：迭代DFS

使用栈实现DFS，记录每一层最右边的节点。

关键点：

1. 使用栈存储节点和深度信息
2. 按照右子树优先的顺序遍历
3. 只在第一次到达该深度时记录节点值

时间复杂度：O(n)，其中n是二叉树的节点数 空间复杂度：O(h)，其中h是二叉树的高度

代码实现

C# 实现

方法一：广度优先搜索（BFS）

public class Solution {
    public IList<int> RightSideView(TreeNode root) {
        var result = new List<int>();
        if (root == null) return result;
        
        var queue = new Queue<TreeNode>();
        queue.Enqueue(root);
        
        while (queue.Count > 0) {
            int levelSize = queue.Count;
            for (int i = 0; i < levelSize; i++) {
                var 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;
    }
}

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

public class Solution {
    private List<int> result = new List<int>();
    
    public IList<int> RightSideView(TreeNode root) {
        if (root == null) return result;
        
        DFS(root, 0);
        return result;
    }
    
    private void DFS(TreeNode node, int depth) {
        if (node == null) return;
        
        if (depth == result.Count) {
            result.Add(node.val);
        }
        
        DFS(node.right, depth + 1);
        DFS(node.left, depth + 1);
    }
}

方法三：迭代DFS

public class Solution {
    public IList<int> RightSideView(TreeNode root) {
        var result = new List<int>();
        if (root == null) return result;
        
        var stack = new Stack<(TreeNode node, int depth)>();
        stack.Push((root, 0));
        
        while (stack.Count > 0) {
            var (node, depth) = stack.Pop();
            
            if (depth == result.Count) {
                result.Add(node.val);
            }
            
            if (node.left != null) {
                stack.Push((node.left, depth + 1));
            }
            if (node.right != null) {
                stack.Push((node.right, depth + 1));
            }
        }
        
        return result;
    }
}

Python 实现

方法一：广度优先搜索（BFS）

class Solution:
    def rightSideView(self, root: TreeNode) -> List[int]:
        if not root:
            return []
            
        result = []
        queue = [root]
        
        while queue:
            level_size = len(queue)
            for i in range(level_size):
                node = queue.pop(0)
                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

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

class Solution:
    def rightSideView(self, root: TreeNode) -> List[int]:
        if not root:
            return []
            
        result = []
        
        def dfs(node: TreeNode, depth: int) -> None:
            if not node:
                return
                
            if depth == len(result):
                result.append(node.val)
                
            dfs(node.right, depth + 1)
            dfs(node.left, depth + 1)
            
        dfs(root, 0)
        return result

方法三：迭代DFS

class Solution:
    def rightSideView(self, root: TreeNode) -> List[int]:
        if not root:
            return []
            
        result = []
        stack = [(root, 0)]
        
        while stack:
            node, depth = stack.pop()
            
            if depth == len(result):
                result.append(node.val)
                
            if node.left:
                stack.append((node.left, depth + 1))
            if node.right:
                stack.append((node.right, depth + 1))
                
        return result

C++ 实现

方法一：广度优先搜索（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;
    }
};

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

class Solution {
private:
    vector<int> result;
    
    void dfs(TreeNode* node, int depth) {
        if (!node) return;
        
        if (depth == result.size()) {
            result.push_back(node->val);
        }
        
        dfs(node->right, depth + 1);
        dfs(node->left, depth + 1);
    }
    
public:
    vector<int> rightSideView(TreeNode* root) {
        if (!root) return result;
        
        dfs(root, 0);
        return result;
    }
};

方法三：迭代DFS

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> result;
        if (!root) return result;
        
        stack<pair<TreeNode*, int>> st;
        st.push({root, 0});
        
        while (!st.empty()) {
            auto [node, depth] = st.top();
            st.pop();
            
            if (depth == result.size()) {
                result.push_back(node->val);
            }
            
            if (node->left) {
                st.push({node->left, depth + 1});
            }
            if (node->right) {
                st.push({node->right, depth + 1});
            }
        }
        
        return result;
    }
};

性能分析

各语言实现的性能对比：

实现语言	方法	执行用时	内存消耗	特点
C#	方法一	92 ms	25.1 MB	BFS方式，直观高效
C#	方法二	88 ms	24.8 MB	DFS方式，代码简洁
C#	方法三	96 ms	25.2 MB	迭代DFS，易于理解
Python	方法一	40 ms	14.9 MB	BFS方式，实现简单
Python	方法二	36 ms	14.8 MB	DFS方式，性能更好
Python	方法三	44 ms	15.1 MB	迭代DFS，代码优雅
C++	方法一	4 ms	12.1 MB	BFS方式，性能优秀
C++	方法二	0 ms	12.0 MB	DFS方式，性能最优
C++	方法三	8 ms	12.2 MB	迭代DFS，实现清晰

补充说明

代码亮点

1. 方法一使用BFS，实现简单直观
2. 方法二使用DFS，代码简洁高效
3. 方法三使用迭代DFS，避免了递归开销

遍历方式解释

• BFS：按层遍历，每层最后一个节点即为右视图节点
• DFS：优先遍历右子树，记录每层第一个访问的节点
• 迭代DFS：使用栈模拟递归，实现DFS遍历

常见错误

1. 没有处理空树的情况
2. BFS方法中没有正确记录每层最后一个节点
3. DFS方法中没有正确处理深度信息
4. 迭代DFS中栈的压入顺序错误

相关题目

• 198. 打家劫舍
• 200. 岛屿数量
• 102. 二叉树的层序遍历