图解LeetCode第 199 号问题:二叉树的右视图

该文已加入开源项目:LeetCodeAnimation(用动画的形式呈现解LeetCode题目的思路,目前 5500 Star )。地址:https://github.com/MisterBooo/LeetCodeAnimation

LeetCode上第 199 号问题:二叉树的右视图

题目描述

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

示例:

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

图解LeetCode第 199 号问题:二叉树的右视图

思路解析

与之前二叉树的层次遍历类似的,该问题需要用到队列,

  • 建立一个queue

  • 遍历每层的节点时,把下一层的节点都存入到queue中

  • 每当开始新一层节点的遍历之前,先把新一层最后一个节点值存到结果中

动画演示

动画演示GIF加载有点慢,请稍等片刻^_^

图解LeetCode第 199 号问题:二叉树的右视图

参考代码

 1class Solution {
2public:
3    vector<int> rightSideView(TreeNode *root) {
4        vector<int> res;
5        if (!root) return res;
6        queue<TreeNode*> q;
7        q.push(root);
8        while (!q.empty()) {
9            res.push_back(q.back()->val);
10            int size = q.size();
11            for (int i = 0; i < size; ++i) {
12                TreeNode *node = q.front();
13                q.pop();
14                if (node->left) q.push(node->left);
15                if (node->right) q.push(node->right);
16            }
17        }
18        return res;
19    }
20};

代码截图

图解LeetCode第 199 号问题:二叉树的右视图


End

关于本号

作者程序员小吴,哈工大学渣,目前正在学算法,开源项目  LeetCodeAnimation 」5500star,GitHub Trending 榜连续一周登顶欢迎大家关注我的微信公众号:五分钟学算法,一起学习,一起进步!

图解LeetCode第 199 号问题:二叉树的右视图


本文由 程序员小吴 创作,采用 CC BY 3.0 CN协议 进行许可。 可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在先添加作者公众号二维码。
五分钟学算法 » 图解LeetCode第 199 号问题:二叉树的右视图

我还会在以下平台发布内容

GitHub 哔哩哔哩