0199. Binary Tree Right Side View
================================
题目信息
--------
:题号: 0199. 二叉树的右视图
:难度: Medium
:主题: 二叉树、广度优先搜索、深度优先搜索、遍历顺序
:原题: `LeetCode 0199 `_
:重点: 把可见节点定义为每层最右节点,用层边界或右优先的深度首次访问精确提交
题目重述
--------
给定一棵二叉树,从右侧观察,返回从上到下能够看到的节点值。每个非空深度恰好返回一个
值,它属于该层结构位置最靠右的节点;空树返回空数组。
“最靠右”由树中位置决定,不是节点值最大,也不保证总在连续的右孩子链上。
自建示例
--------
.. code-block:: text
1
/ \
2 3
\ \
5 4
每层从左到右:[1]、[2,3]、[5,4]
输出:[1,3,4]
.. code-block:: text
1
/ \
2 3
/
4
/
5
输出:[1,3,4,5]
右分支提前结束后,更深层的可见节点来自左子树,不能只沿 right 指针向下走。
C++ 实现
--------
.. code-block:: cpp
#include
#include
#include
class Solution {
private:
std::vector breadthFirstLevels(TreeNode* root) {
if (root == nullptr) {
return {};
}
std::queue pending;
std::vector visible;
pending.push(root);
while (!pending.empty()) {
std::size_t level_size = pending.size();
for (std::size_t index = 0;
index < level_size;
++index) {
TreeNode* node = pending.front();
pending.pop();
if (node->left != nullptr) {
pending.push(node->left);
}
if (node->right != nullptr) {
pending.push(node->right);
}
if (index + 1 == level_size) {
visible.push_back(node->val);
}
}
}
return visible;
}
void visitRightFirst(
TreeNode* node, int depth, std::vector& visible) {
if (node == nullptr) {
return;
}
if (depth == static_cast(visible.size())) {
visible.push_back(node->val);
}
visitRightFirst(node->right, depth + 1, visible);
visitRightFirst(node->left, depth + 1, visible);
}
std::vector depthFirstLevels(TreeNode* root) {
std::vector visible;
visitRightFirst(root, 0, visible);
return visible;
}
public:
std::vector rightSideView(TreeNode* root) {
return breadthFirstLevels(root);
}
};
题解
----
观察对象是层而不是路径
~~~~~~~~~~~~~~~~~~~~~~
只沿 ``right`` 指针前进,相当于假设每一层最右节点都是上一层最右节点的右孩子。第二棵
示例在深度 2、3 立即反驳了这个假设:右子树没有节点,但左子树仍延伸,节点 4、5 依然能
从右侧看到。
把整棵树序列化并记录所有空位置,也能恢复每层最右非空节点,却保存了题目不需要的完整
结构。真正需要的是对每个深度提交一个最右节点;BFS 直接把搜索空间分成层,DFS 则通过
访问顺序让最右节点成为该深度的第一次访问。
主解:队列如何保持层内次序
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
``breadthFirstLevels`` 的外层每轮开始时,队列恰好以从左到右顺序保存当前层全部非空节点。
根层显然成立。处理当前层时,父节点从左到右出队,每个父节点又先加入左孩子、再加入右
孩子,所以形成的下一层队列仍从左到右。
当前层最后出队的节点因此就是该层最右非空节点。代码只在
``index + 1 == level_size`` 时把其值加入答案,其他同层节点仅用于发现下一层。
层大小为什么必须冻结
~~~~~~~~~~~~~~~~~~~~~~
``level_size = pending.size()`` 是本轮开始时的快照。层内处理会不断把孩子加入队尾,队列
长度随之变化;若循环条件直接追随实时 ``pending.size()``,新孩子会被当成当前层继续处理,
层边界消失,也就无法知道哪个节点是某一深度的最后一个。
只弹出快照中的 ``level_size`` 个节点后,旧层恰好清空,队列只剩下一层。每轮提交一次,
保证输出深度从根到叶递增且不重不漏。
BFS 状态走读
~~~~~~~~~~~~
对第一棵示例树,队列按头到尾书写:
.. code-block:: text
层 轮开始队列 冻结大小 本层最后节点 轮结束队列
0 [1] 1 1 [2,3]
1 [2,3] 2 3 [5,4]
2 [5,4] 2 4 []
得到 ``[1,3,4]``。节点值大小没有参与选择;即使 5 大于 4,位置更靠右的 4 才可见。
替代方案:右优先 DFS
~~~~~~~~~~~~~~~~~~~~
深度优先搜索不天然按层结束,但可以改变同一深度的到达顺序。先递归右子树、再递归左子树
时,每个深度第一次访问到的节点就是能从右侧优先遇到的节点。
``visible.size()`` 等于已经提交的深度数。到达 ``depth`` 时:
* 若 ``depth == visible.size()``,此前尚未访问该深度,当前节点是右优先顺序中的第一个,
应提交;
* 若 ``depth < visible.size()``,该深度已有更靠右节点,当前值不能覆盖它。
随后仍必须递归左子树。右子树可能没有足够深,左侧后代会成为某个新深度的第一次访问,
正如第二棵示例中的 4、5。右优先不是“只走右边”,而是定义同层候选的优先级。
两个方案的正确性与取舍
~~~~~~~~~~~~~~~~~~~~~~
BFS 通过层大小不变量证明每轮快照是完整一层,最后节点即最右节点;DFS 通过右先左后的
遍历顺序证明每个深度首次到达者最右,之后同深度节点被忽略。两者都访问每个节点一次,
时间为 ``O(n)``,也都只读树。
BFS 队列峰值为最大层宽 ``O(w)``,层边界与题意直接对应,因此作为主解;DFS 使用
``O(h)`` 递归栈,在窄深树上空间更小,但极深树存在调用栈风险。返回数组本身包含每层一个
值,大小 ``O(h)``,属于必要输出载荷。