前言
二叉树层序遍历应用题目。
记录三十八 【二叉树的层次遍历应用一】
继续。
一、【107.二叉树的层次遍历 II】
题目
给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：[[15,7],[9,20],[3]]
示例 2：
输入：root = [1]
输出：[[1]]
示例 3：
输入：root = []
输出：[]
提示：
树中节点数目在范围 [0, 2000] 内
-1000 <= Node.val <= 1000
思路
题目的意思是从底层逐步往上输出，相当于【102.二叉树的层序遍历】 倒着输出。
那么reverse，从上到下的结果？加一句reverse(result.begin(),result.end());
代码实现
/**
* 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<vector<int>> levelOrderBottom(TreeNode* root) {
vector<vector<int>> result;
queue<TreeNode*> que;
if(root != nullptr) que.push(root);
while(!que.empty()){
int size = que.size(); //在还没遍历这一层时，先把这一层的元素个数记录下来。
vector<int> levelrecord;
while(size--){ //边遍历边放入下一层元素。
TreeNode* top = que.front();
que.pop();
if(top->left) que.push(top->left);
if(top->right) que.push(top->right);
levelrecord.push_back(top->val);
}
result.push_back(levelrecord);
}
reverse(result.begin(),result.end()); //新增一行
return result;
}
};
二、【199.二叉树的右视图】
题目
给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
示例 1:
输入: [1,2,3,null,5,null,4]
输出: [1,3,4]
示例 2:
输入: [1,null,3]
输出: [1,3]
示例 3:
输入: []
输出: []
提示:
二叉树的节点个数的范围是 [0,100]
-100 <= Node.val <= 100
思路
（1）如果只从示例1，考虑右视图只看右孩子，右孩子的右孩子，……。这样如果右孩子为空，左孩子的右孩子也在右视图的范围内。不合理。
（2）仍然遍历每一层的节点，但是当该层的最后一个节点出去的时候，放到result中。
代码实现
/**
* 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> result;
queue<TreeNode*> que;
if(root != nullptr) que.push(root);
while(!que.empty()){
int size = que.size();
while(size--){
TreeNode* cur = que.front();
que.pop();
if(cur->left) que.push(cur->left);
if(cur->right) que.push(cur->right);
if(size == 0){
result.push_back(cur->val);
}
}
}
return result;
}
};
参考思路链接
思路一致，不过参考代码用的循环时for而已。
三、【637.二叉树的层平均值】
题目
给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：[3.00000,14.50000,11.00000]
解释：第 0 层的平均值为 3,第 1 层的平均值为 14.5,第 2 层的平均值为 11 。
因此返回 [3, 14.5, 11] 。
示例 2:
输入：root = [3,9,20,15,7]
输出：[3.00000,14.50000,11.00000]
提示：
树中节点数量在 [1, 10^4] 范围内
-2^31 <= Node.val <= 2^31 - 1
思路
每层遍历后sum求和除以size。所以不能用while(size- -)循环，size会改变。改成for循环。
代码实现
/**
* 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<double> averageOfLevels(TreeNode* root) {
vector<double> result;
queue<TreeNode*> que;
if(root != nullptr) que.push(root);
while(!que.empty()){
int size = que.size();
double sum = 0;
for(int i=0;i <size;i++){
TreeNode* cur = que.front();
que.pop();
if(cur->left) que.push(cur->left);
if(cur->right) que.push(cur->right);
sum += cur->val;
}
result.push_back(sum/size); //不能用size--，while循环。不然此处的size发生改变。
}
return result;
}
};
四、实现二叉树的结构
力扣题目输入root = [3,9,20,null,null,15,7]，代表构造一个二叉树。那么具体如何实现，力扣不考察。
但是就给定输入vector< string > root = [3,9,20,null,null,15,7]，实现二叉树的构造，这一函数练习一下。（相当于ACM模式下创建二叉树）
#include <string>
#include <vector>
#include <iostream>
#include <queue>
using namespace std;
//定义节点结构
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) {}
};
//构造二叉树
TreeNode* createTree(vector<string> tree){
queue<TreeNode*> que;
if(tree.empty()) return nullptr;
TreeNode* root = new TreeNode(stoi(tree[0]));
que.push(root);
int i = 0;
while(!que.empty()){
TreeNode* cur = que.front();
que.pop();
//创建左孩子
if((2*i+1) < tree.size() && tree[2*i+1] != "null"){
TreeNode* leftchild = new TreeNode(stoi(tree[2*i+1]));
que.push(leftchild);
cur->left = leftchild;
}
//创建右孩子
if((2*i+2) < tree.size() && tree[2*i+2] != "null"){
TreeNode* rightchild = new TreeNode(stoi(tree[2*i+2]));
que.push(rightchild);
cur->right = rightchild;
}
i++;
}
return root;
}
//销毁二叉树，用递归法，练习递归，走后序遍历的流程
void destoryTree(TreeNode* root){
if(root == nullptr){
return;
}
destoryTree(root->left);
destoryTree(root->right);
delete root;
}
int main(){
vector<string> tree = {"3","9","20","null","null","15","7"};
TreeNode* root = createTree(tree);
destoryTree(root);
return 0;
}
总结
- 前三点，利用层序遍历的模版，使用队列结构，遍历每层的练习题；
- 最后，从0实现实现一个二叉树创建、销毁、定义。
（欢迎指正，转载标明出处）
