一、层序遍历
层序遍历，是按照层数从低到高，同一层从左到右遍历。在这里采用递归法是无法做到的，观察遍历的特点，这里需再加一个队列来实现。
天津网站制作公司哪家好，找
创新互联！从网页设计、网站建设、微信开发、APP开发、
自适应网站建设等网站项目制作，到程序开发，运营维护。
创新互联公司2013年成立到现在10年的时间，我们拥有了丰富的建站经验和运维经验，来保证我们的工作的顺利进行。专注于网站建设就选
创新互联。
在将一层一层的二叉树节点放入队列以及弹出队列的操作中，需要记录和知道弹出的个数size。
具体思路和步骤如代码：
102.二叉树的层序遍历 #力扣题目链接
class Solution {
public:
vector>levelOrder(TreeNode* root) {
queueque;
vector>result;
if(root != NULL) que.push(root); //弹入根节点
while(!que.empty()){
int size = que.size(); //记录size个数
vectorvec; //记录某一层的结果
while(size--){
TreeNode* node = que.front(); //获取要弹出的节点
que.pop(); //队列弹出
vec.push_back(node->val); //将弹出的节点数值放入数组中
if(node->left) que.push(node->left); //获取这个节点的左孩子
if(node->right) que.push(node->right); //获取这个节点的右孩子
}
result.push_back(vec); //将一层的数组放入到结果中
}
return result;
}
};
107.二叉树的层序遍历②#力扣题目链接
在102的基础上进行结果翻转即可。
reverse(result.begin(), result.end());
199.二叉树的右视图#力扣题目链接
这道题的核心思想：就是将每一层弹出的最后一个放入结果数组中，就可以了。
class Solution {
public:
vectorrightSideView(TreeNode* root) {
queueque;
vectorresult;
if(root != NULL) que.push(root); //弹入根节点
while(!que.empty()){
int size = que.size(); //记录size个数
while(size--){
TreeNode* node = que.front(); //获取要弹出的节点
que.pop(); //队列弹出
if(size == 0){
result.push_back(node->val); //最后一个弹出的放入结果数组即可
}
if(node->left) que.push(node->left); //获取这个节点的左孩子
if(node->right) que.push(node->right); //获取这个节点的右孩子
}
}
return result;
}
};
637.二叉树的层平均值 #力扣题目链接
这一道题的思路：在每一层的元素弹出时，记录下来并进行加和，在每一层弹出结束后将再将平均数放到result数组中即可。
class Solution {
public:
vectoraverageOfLevels(TreeNode* root) {
double sum = 0; //记录求和
vectorresult;
queueque;
if(root != NULL) que.push(root);
while(!que.empty()){
int size = que.size();
double count = 0; //记录某一层的元素个数
double sum = 0; //记录所有数的加和
while(size--){
TreeNode* node = que.front();
que.pop();
count++;
sum += node->val;
if(node->left) que.push(node->left);
if(node->right) que.push(node->right);
}
result.push_back(sum / count); //将每一层的平均数放到数组里
}
return result;
}
};
429.N叉树的层序遍历#力扣题目链接
n叉树和二叉树的层序遍历区别不大，这里将left、right变换成children[i]就可以了。
class Solution {
public:
vector>levelOrder(Node* root) {
queueque;
vector>result;
if(root != NULL) que.push(root); //弹入根节点
while(!que.empty()){
int size = que.size(); //记录size个数
vectorvec; //记录某一层的结果
while(size--){
Node* node = que.front(); //获取要弹出的节点
que.pop(); //队列弹出
vec.push_back(node->val); //将弹出的节点数值放入数组中
for(int i = 0; i< node->children.size(); i++){
if(node->children[i]) que.push(node->children[i]);
}
}
result.push_back(vec); //将一层的数组放入到结果中
}
return result;
}
};
515.在每个树行中找大值 #力扣题目链接
这道题，在每层进行比较即可获得大值即可。
class Solution {
public:
vectorlargestValues(TreeNode* root) {
queueque;
vectorresult;
if(root != NULL) que.push(root); //弹入根节点
while(!que.empty()){
int size = que.size(); //记录size个数
int max = INT32_MIN; //记录大值
while(size--){
TreeNode* node = que.front(); //获取要弹出的节点
que.pop(); //队列弹出
if(node->val >max){ //进行数值的比较，获得大值
max = node->val;
}
if(node->left) que.push(node->left); //获取这个节点的左孩子
if(node->right) que.push(node->right); //获取这个节点的右孩子
}
result.push_back(max);
}
return result;
}
};
116.填充每个节点的下一个右侧节点指针#力扣题目链接
这里类似于链表操作，记录好上一个元素nodePre即可，之后将next指针指向下一个元素即可。
class Solution {
public:
Node* connect(Node* root) {
queueque;
if(root != NULL) que.push(root); //弹入根节点
while(!que.empty()){
int size = que.size(); //记录size个数
Node* nodePre;
Node* node;
for(int i = 0; inext = node;
nodePre = nodePre->next;
}
if(node->left) que.push(node->left); //获取这个节点的左孩子
if(node->right) que.push(node->right); //获取这个节点的右孩子
}
nodePre->next = NULL;
}
return root;
}
};
117.填充每个节点的下一个右侧节点指针2#力扣题目链接
解题逻辑和116一模一样。
104.二叉树的大深度#力扣题目链接
在遍历的同时，记录层数即可。
class Solution {
public:
int maxDepth(TreeNode* root) {
queueque;
int result = 0; //记录层数
if(root != NULL) que.push(root); //弹入根节点
while(!que.empty()){
int size = que.size(); //记录size个数
while(size--){
TreeNode* node = que.front(); //获取要弹出的节点
que.pop(); //队列弹出
if(node->left) que.push(node->left); //获取这个节点的左孩子
if(node->right) que.push(node->right); //获取这个节点的右孩子
}
result++;
}
return result;
}
};
111.二叉树的最小深度#力扣题目链接
判断条件：当左右孩子为空时，说明到遍历的最低点了。
class Solution {
public:
int minDepth(TreeNode* root) {
if (root == NULL) return 0;
int result = 0;
queueque;
que.push(root);
while(!que.empty()) {
int size = que.size();
result++; // 记录最小深度
for (int i = 0; i< size; i++) {
TreeNode* node = que.front();
que.pop();
if (node->left) que.push(node->left);
if (node->right) que.push(node->right);
if (!node->left && !node->right) { // 当左右孩子都为空的时候
return result;
}
}
}
return result;
}
};
二、翻转二叉树
题目：#力扣题目链接
给你一棵二叉树的根节点 root，翻转这棵二叉树，并返回其根节点。
这道题解决的方法，先需要确定遍历方式，采用前序和后序遍历方式比较好，这里只需要进行左右孩子的交换即可。
class Solution {
public:
void traversal(TreeNode *cur, vector& dep){ //前序遍历
if(cur == NULL) return;
dep.push_back(cur->val); //中
swap(cur->left, cur->right); //交换左右孩子
traversal(cur->left, dep); //左
traversal(cur->right, dep); //右
}
TreeNode* invertTree(TreeNode* root) {
vectorresult;
traversal(root, result);
return root;
}
};
三、对称二叉树
题目：#力扣题目链接
给你一个二叉树的根节点 root， 检查它是否轴对称。
这道题判断是二叉树是否为对称二叉树，即左右孩子是否可以翻转不变，体现在外侧节点和内侧节点是否相等。
所以需要不停的判断左右孩子的信息，之后返回到根节点，这里采用遍历方式就应该只能采取后序遍历。
class Solution {
public:
bool compare(TreeNode* left, TreeNode* right){
//这里判断条件需要理解透彻，容易出错
if(left == NULL && right != NULL) return false;
else if(left != NULL && right == NULL) return false;
else if(left == NULL && right == NULL) return true;
else if(left->val != right->val) return false;
bool outside = compare(left->left, right->right);
bool inside = compare(left->right, right->left);
bool result = outside && inside;
return result;
}
bool isSymmetric(TreeNode* root) {
if(root == NULL) return true;
return compare(root->left, root->right);
}
};
四、总结和收获
在这一章节，需要我们去了解二叉树几种遍历方式的特点，并在实现过程中有意识的去分析采用那种遍历方式。
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
本文名称：代码随想录第15天：二叉树-创新互联
文章起源：
http://cdkjz.cn/article/deehho.html
