二叉树的右视图
程序员文章站
2022-04-24 23:13:17
...
从二叉树右侧观察,层次遍历,每一层的最后一个结点就是观察到的那个结点
将结点和层数绑定为pair,压入队列时,记录每一层中的最后一个结点.
/**
* 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;//保存结果
queue<pair<TreeNode*,int> > q;//层序遍历用的队列,<结点,对应的层数>
if(root)
q.push(make_pair(root,0));
while(!q.empty())//和写层序遍历一样
{
TreeNode* node = q.front().first;
int depth = q.front().second;
q.pop();
if(view.size() == depth)//说明到了新的一层
{
view.push_back(node->val);
}else{
view[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;
}
};