二叉树的右视图

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

解法一（层序遍历）：

/**
 * 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 == nullptr)
        {
            return ans;
        }

        queue<TreeNode*> q;
        q.push(root);

        while (!q.empty())
        {
            int size = q.size();

            for (int i = 0; i < size; ++i)
            {
                TreeNode* node = q.front();
                q.pop();

                if (i == size - 1)
                {
                    ans.push_back(node->val);
                }

                if (node->left != nullptr)
                {
                    q.push(node->left);
                }

                if (node->right != nullptr)
                {
                    q.push(node->right);
                }
            }
        }

        return ans;
    }
};

解法二（右优先 DFS）：

/**
 * 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;
        dfs(root, 0, ans);
        return ans;
    }

private:
    void dfs(TreeNode* node, int depth, vector<int>& ans) {
        if (node == nullptr)
        {
            return;
        }

        if (depth == ans.size())
        {
            ans.push_back(node->val);
        }

        dfs(node->right, depth + 1, ans);
        dfs(node->left, depth + 1, ans);
    }
};

核心思想

右视图要返回的是每一层从右侧能看到的那个节点。

如果按层看一棵二叉树，那么每一层最右边的节点会挡住这一层左边的节点。

所以问题可以转化为：

找出二叉树每一层最右边的节点。

最直接的做法是层序遍历。

每次处理一整层节点，这一层最后被访问到的节点，就是这一层最右边的节点。

另一种做法是 DFS。

如果每一层都先访问右子树，那么某个深度第一次被访问到的节点，就是这一层从右边看到的节点。

解法一：层序遍历

层序遍历使用队列按层处理节点。

每一轮循环开始时，队列中的节点正好是当前层的全部节点。

先记录当前层节点数量：

int size = q.size();

然后连续处理 size 个节点。

如果当前处理的是这一层的最后一个节点：

if (i == size - 1)
{
    ans.push_back(node->val);
}

就把它加入答案。

因为代码先加入左孩子，再加入右孩子：

q.push(node->left);
q.push(node->right);

所以队列中同一层节点的访问顺序是从左到右。

因此每层最后一个被访问到的节点，就是这一层最右边的节点。

队列中存什么

队列中保存的是还没有处理的节点：

queue<TreeNode*> q;

初始时，如果根节点不为空，就把根节点放入队列。

之后每处理一个节点，就把它的非空左孩子和右孩子加入队列。

由于队列是先进先出结构，上一层的节点会先被处理，下一层的节点会留到下一轮。

这样就能保证按照从上到下的顺序处理整棵树。

解法二：右优先 DFS

DFS 写法使用深度 depth 表示当前节点所在层数。

根节点深度为 0。

如果当前深度还没有加入过答案：

if (depth == ans.size())
{
    ans.push_back(node->val);
}

说明当前节点是这一层第一个被访问到的节点。

因为递归时先访问右子树：

dfs(node->right, depth + 1, ans);
dfs(node->left, depth + 1, ans);

所以每一层第一次被访问到的节点，一定是这一层最靠右的节点。

因此可以直接加入答案。

如果后面左子树中也有同一层节点，因为 depth < ans.size()，不会再覆盖答案。

为什么右优先 DFS 正确

普通 DFS 如果先访问左子树，那么每层第一次访问到的节点会是左侧节点。

右视图需要的是每层最右侧节点。

所以只需要把访问顺序改成：

当前节点 -> 右子树 -> 左子树

这样右边节点会优先占据对应深度的答案位置。

当递归走到某个深度时，如果这是第一次到达这个深度，就说明之前没有任何更靠右的节点到达过这一层。

当前节点就应该被右视图看到。

边界情况

如果二叉树为空：

root = []

没有任何节点能被看到，直接返回空数组 []。

如果二叉树只有一个节点，那么右视图只包含根节点。

如果某一层只有左节点，没有右节点，那么从右侧仍然能看到这个左节点。

例如：

root = [1,2,null]

右视图是：

[1,2]

如果树退化成一条链，无论链向左还是向右，每一层都只有一个节点，这些节点都会出现在右视图中。

正确性证明

我们证明：两个解法都能正确返回二叉树的右视图。

结论 1：层序遍历每轮恰好处理一层节点

每轮循环开始时，算法记录：

int size = q.size();

此时队列中的节点正好是当前层的节点。

循环只执行 size 次。

在循环过程中加入队列的孩子节点都属于下一层，不会在当前轮被处理。

所以每轮循环恰好处理一层节点。

结论 2：层序遍历每层加入的是最右边节点

层序遍历中，算法先把左孩子入队，再把右孩子入队。

因此同一层节点会按照从左到右的顺序被处理。

由结论 1 可知，每轮处理的是同一层的全部节点。

所以当 i == size - 1 时，当前节点就是这一层最右边的节点。

算法把它加入答案，符合右视图要求。

结论 3：右优先 DFS 每层第一次访问到的是最右边节点

DFS 访问顺序是：

当前节点 -> 右子树 -> 左子树

对于同一深度，右侧路径上的节点会比左侧路径上的节点更早被访问。

如果某个深度第一次被访问到，说明这一层还没有记录任何节点。

由于算法总是优先走右子树，这个第一次访问到的节点就是这一层最右边能看到的节点。

所以把它加入答案是正确的。

结论 4：右优先 DFS 不会错误覆盖答案

当某个深度已经加入过节点后，ans.size() 已经大于这个深度。

后续再访问到同一深度的左侧节点时，不满足：

depth == ans.size()

因此不会再次加入或覆盖该层答案。

所以每一层最终只会保留最早访问到的右侧节点。

得出结论

由结论 1 和结论 2 可知，层序遍历解法能正确选出每层最右边节点。

由结论 3 和结论 4 可知，右优先 DFS 解法也能正确选出每层最右边节点。

因此两个解法都能正确返回二叉树的右视图。

举例理解

以：

root = [1,2,3,null,5,null,4]

为例，这棵树可以理解为：

    1
   / \
  2   3
   \   \
    5   4

从右侧看：

• 第 1 层只能看到 1
• 第 2 层最右边是 3
• 第 3 层最右边是 4

所以答案是：

[1,3,4]

用层序遍历看过程：

最终返回：

[1,3,4]

复杂度分析

设二叉树节点数为 n，树的高度为 h，树的最大宽度为 w。

解法一

每个节点最多入队一次、出队一次。

• 时间复杂度：O(n)
• 空间复杂度：O(w)

空间复杂度来自队列，队列最多同时保存一层节点。

解法二

每个节点最多被 DFS 访问一次。

• 时间复杂度：O(n)
• 空间复杂度：O(h)

空间复杂度来自递归调用栈。