Leetcode199二叉树右视图[C++题解]:BFS+层数

文章目录

• • 题目
  • 思路
  • 提交代码（ac代码）
  • 测试代码

题目

Leetcode199二叉树右视图

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

示例:

输入: [1,2,5,4,5,6] 输出: [1, 5, 6] 解释:1 <---/ \ 2 5 <--- / \ \ 4 5 6 <---

思路

层次遍历二叉树，也就是广度优先搜索BFS
这里需要做的是如何把每一层最后一个元素进行标记。
我们把节点和它所在的层数组在一起同时入队列Q。

queue<pair<TreeNode*,int> > Q;

然后可以求解层数的问题

提交代码（ac代码）

/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/ class Solution { public:vector<int> rightSideView(TreeNode* root){vector<int> view;//save the resultqueue<pair<TreeNode*,int> > Q;if(root)Q.push(make_pair(root,0));//root and its level 0while(!Q.empty()){TreeNode* node=Q.front().first;//current nodeint depth=Q.front().second;//level of the nodeQ.pop();if(view.size()==depth)//每行第一个 view.push_back(node->val);elseview[depth]=node->val;//每行只存一个，不断更新 if(node->left)Q.push(make_pair(node->left,depth+1));if(node->right)Q.push(make_pair(node->right,depth+1)); }return view;} };

测试代码

#include<iostream>#include<vector>#include<queue>using namespace std;struct TreeNode{int val;TreeNode* left;TreeNode* right;TreeNode(int x):val(x),left(NULL),right(NULL){} };vector<int> rightSideView(TreeNode* root){vector<int> view;//save the resultqueue<pair<TreeNode*,int> > Q;if(root)Q.push(make_pair(root,0));//root and its level 0while(!Q.empty()){TreeNode* node=Q.front().first;//current nodeint depth=Q.front().second;//level of the nodeQ.pop();if(view.size()==depth)//每行第一个 view.push_back(node->val);elseview[depth]=node->val;//每行只存一个，不断更新 if(node->left)Q.push(make_pair(node->left,depth+1));if(node->right)Q.push(make_pair(node->right,depth+1)); }return view;}int main(){TreeNode a(1);TreeNode b(2);TreeNode c(5);TreeNode d(3);TreeNode e(4);TreeNode f(6);a.left=&b;a.right=&c;c.right=&f;b.left=&d;b.right=&e;vector<int> test;test=rightSideView(&a);for(size_t i=0;i<test.size();++i)cout<<test[i]<<"";return 0;}

测试结果

总结

以上是生活随笔为你收集整理的Leetcode199二叉树右视图[C++题解]:BFS+层数的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。