LC 199. 二叉树的右视图

题目描述

这是 LeetCode 上的 199. 二叉树的右视图 ，难度为中等。

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

示例 1:

1
2
3

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

输出: [1,3,4]

示例 2:

1
2
3

输入: [1,null,3]

输出: [1,3]

示例 3:

1
2
3

输入: []

输出: []

提示:

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

BFS

本质就是找层序遍历过程中，每层的最后一个节点。

Java 代码：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if (root == null) return ans;
        Deque<TreeNode> d = new ArrayDeque<>();
        d.addLast(root);
        while (!d.isEmpty()) {
            int sz = d.size();
            while (sz-- > 0) {
                TreeNode node = d.pollFirst();
                if (node.left != null) d.addLast(node.left);
                if (node.right != null) d.addLast(node.right);
                if (sz == 0) ans.add(node.val);
            }
        }
        return ans;
    }
}

C++ 代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> ans;
        if (!root) return ans;
        queue<TreeNode*> d;
        d.push(root);
        while (!d.empty()) {
            int sz = d.size();
            while (sz-- > 0) {
                TreeNode* node = d.front();
                d.pop();
                if (node->left) d.push(node->left);
                if (node->right) d.push(node->right);
                if (sz == 0) ans.push_back(node->val);
            }
        }
        return ans;
    }
};

Python 代码：

# 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]:
        ans = []
        if not root:
            return ans
        d = deque()
        d.append(root)
        while d:
            sz = len(d)
            while sz > 0:
                node = d.popleft()
                if node.left:
                    d.append(node.left)
                if node.right:
                    d.append(node.right)
                if sz == 1:
                    ans.append(node.val)
                sz -= 1
        return ans

TypeScript 代码：

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */
function rightSideView(root: TreeNode | null): number[] {
    const ans = [];
    if (!root) return ans;
    const d = [];
    d.push(root);
    while (d.length > 0) {
        let sz = d.length;
        while (sz-- > 0) {
            const node = d.shift()!;
            if (node.left) d.push(node.left);
            if (node.right) d.push(node.right);
            if (sz === 0) ans.push(node.val);
        }
    }
    return ans;
};

时间复杂度：$O(n)$
空间复杂度：$O(n)$

DFS

DFS 解法同理，规定好节点的遍历顺序（例如 中-右-左），并在 DFS 过程中传递当前层参数 level（根节点为第 0 层），同时使用一个 Set 数据结构记录处理过的层编号，从而实现只将当前层的首个节点添加到答案中。

Java 代码：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<Integer> ans = new ArrayList<>();
    Set<Integer> set = new HashSet<>();
    public List<Integer> rightSideView(TreeNode root) {
        dfs(root, 0);
        return ans;
    }
    void dfs(TreeNode node, int level) {
        if (node == null) return ;
        if (!set.contains(level)) {
            ans.add(node.val);
            set.add(level);
        }
        dfs(node.right, level + 1);
        dfs(node.left, level + 1);
    }
}

C++ 代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> ans;
    unordered_set<int> levels;
    vector<int> rightSideView(TreeNode* root) {
        dfs(root, 0);
        return ans;
    }
    void dfs(TreeNode* node, int level) {
        if (!node) return;
        if (levels.find(level) == levels.end()) {
            ans.push_back(node->val);
            levels.insert(level);
        }
        dfs(node->right, level + 1);
        dfs(node->left, level + 1);
    }
};

Python 代码：

# 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]:        
        def dfs(node, level):
            if not node:
                return
            if level not in levels:
                ans.append(node.val)
                levels.add(level)
            dfs(node.right, level + 1)
            dfs(node.left, level + 1)
        ans = []
        levels = set()
        dfs(root, 0)
        return ans

TypeScript 代码：

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */
function rightSideView(root: TreeNode | null): number[] {
    const ans = [];
    const levels = new Set();
    function dfs(node: TreeNode | null, level: number) {
        if (!node) return;
        if (!levels.has(level)) {
            ans.push(node.val);
            levels.add(level);
        }
        dfs(node.right, level + 1);
        dfs(node.left, level + 1);
    }
    dfs(root, 0);
    return ans;
};

时间复杂度：$O(n)$
空间复杂度：$O(n)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.198 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

DFS BFS 二叉树层序遍历

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

LC 2876. 有向图访问计数上一篇

LC 剑指 Offer 20. 表示数值的字符串下一篇