当前位置：首页 > news >正文

力扣9.2

news 来源：原创 2024/9/20 21:43:47

199.二叉树的右视图

题目

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

数据范围

二叉树的节点个数的范围是 [0,100]
-100 <= Node.val <= 100

分析

树的层次遍历，每次返回那一层最边上的元素，可以使用两个deque实现

代码

/*** 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:deque<TreeNode*> tmp, ve;vector<int> res; void bfs(TreeNode* q) {ve.push_back(q);while(ve.size()) {tmp = ve;res.push_back(ve.back()->val);ve.clear();while(tmp.size()) {auto now = tmp.front();tmp.pop_front();auto l = now -> left, r = now -> right;if(l != nullptr) ve.push_back(l);if(r != nullptr) ve.push_back(r);}}}vector<int> rightSideView(TreeNode* root) {if(root == nullptr) return res;bfs(root);return res;}
};

637.二叉树的层平均值

题目

给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。

数据范围

树中节点数量在[1, 104] 范围内
-2^31 <= Node.val <= 2^31 - 1

分析

使用两个vector实现树的层次遍历

代码

/*** 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<TreeNode*> tmp1, tmp2;vector<double> res;void bfs(TreeNode* p) {tmp2.push_back(p);while(tmp2.size()) {tmp1 = tmp2;tmp2.clear();double ave = 0;double cnt = 0;while(tmp1.size()) {auto now = tmp1.back();ave += now -> val;cnt += 1;tmp1.pop_back();auto l = now -> left, r = now -> right;if(l != nullptr) tmp2.push_back(l);if(r != nullptr) tmp2.push_back(r);}res.push_back(ave / cnt);}} vector<double> averageOfLevels(TreeNode* root) {bfs(root);return res;}
};