HHot 100C++ 图解

199. 二叉树的右视图

中等 二叉树 3 帧动画 在力扣上做

一句话套路BFS 每层最后一个结点

题目描述

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

思路

时间O(n)
空间O(宽度)

思路

层序遍历,每层取最后一个。

也可用 DFS(根->右->左 的顺序,第一次到达某深度时记录),两种写法都是高频追问点。

图解

2 5 1 3 4
二叉树(来自本仓库测试数据,nullopt 表示空位)

逐帧动画

1 / 3

快捷键:← → 单步,空格播放 / 暂停。

C++17 题解

src/08_binary_tree.cpp21 行
namespace lc0199 {
class Solution {
 public:
  vector<int> rightSideView(TreeNode* root) {
    vector<int> ans;
    if (!root) return ans;
    queue<TreeNode*> q{{root}};
    while (!q.empty()) {
      int sz = (int)q.size();
      for (int i = 0; i < sz; ++i) {
        TreeNode* cur = q.front();
        q.pop();
        if (i == sz - 1) ans.push_back(cur->val);  // 本层最右
        if (cur->left) q.push(cur->left);
        if (cur->right) q.push(cur->right);
      }
    }
    return ans;
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q199_right_side_view8 行
lc0199::Solution s;
TreeNode* a = buildTree({1, 2, 3, nullopt, 5, nullopt, 4});
CHECK_EQ(s.rightSideView(a), vector<int>{1, 3, 4});
freeTree(a);
TreeNode* b = buildTree({1, 2, 3, nullopt, 5});  // 右侧缺,取到 5
CHECK_EQ(s.rightSideView(b), vector<int>{1, 3, 5});
freeTree(b);
CHECK_EQ(s.rightSideView(nullptr), vector<int>{});

↑↓ 选择↵ 打开/ 随时唤起