代码随想录算法训练营第十四天 | 层序遍历、226.翻转二叉树、101.对称二叉树

本文主要是介绍代码随想录算法训练营第十四天 | 层序遍历、226.翻转二叉树、101.对称二叉树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

层序遍历

层序遍历，就是从左到右一层层的去遍历二叉树，这种遍历方式就是图论中的广度优先遍历。实现广度优先遍历，需要借助队列这个数据结构来实现。层序遍历的模板如下：

class Solution{public:vector<vector<int>> levelOrder(TreeNode* root){queue<TreeNode*> que;if(root != nullptr) que.push(root);vector<vector<int>> result;while(!que.empty()){int size = que.size();vector<int> vec;// 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的for(int i = 0;i<size;i++){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;}
};

递归法的模板如下：

class Solution{
public:void order(TreeNode* cur, vector<vector<int>>& result, int depth){if(cur == nullptr) return;if(result.size() == depth) result.push_back(vector<int>());result[depth].push_back(cur->val);order(cur->left, result, depth + 1);order(cur->right, result, depth + 1);}vector<vector<int>> levelOrder(TreeNode* root){vector<vector<int>> result;int depth = 0;order(root, result, depth);return result;}
};

利用模板，可以一连打十道题，如下：

102. 二叉树的层序遍历

思路：标准的层序遍历，利用上述的版子就可以解答

107. 二叉树的层序遍历 II

思路：先做层序遍历，然后将结果反转

199. 二叉树的右视图

思路：进行层次遍历，每次将每层的最后一个节点的值添加到结果中

637. 二叉树的层平均值

思路：进行层次遍历，然后对每层的结果做平均，注意每个节点的数值是否越过int的边界

429. N 叉树的层序遍历

思路：和二叉树的层序遍历类似，采用队列作为容器来实现

515. 在每个树行中找最大值

思路：用层序方式进行遍历，然后找出每层中的最大值，添加入结果

116. 填充每个节点的下一个右侧节点指针

思路：进行层序遍历，然后在遍历的过程中不断地将每层的前一个节点指向后一个节点

117. 填充每个节点的下一个右侧节点指针 II

思路：这题和上一题一模一样，进行层序遍历，然后把前一个节点指向后一个节点

104. 二叉树的最大深度

思路：可以采用层序遍历来解决，每一层记一次数，总数就是二叉树的最大深度

111. 二叉树的最小深度

思路：进行层次遍历，如果在遍历时，发现当前有一个节点既没有左子树又没有右子树，则当前节点的深度为二叉树的最小深度

226.翻转二叉树

题目链接：226. 翻转二叉树
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

文章讲解/视频讲解：https://programmercarl.com/0226.%E7%BF%BB%E8%BD%AC%E4%BA%8C%E5%8F%89%E6%A0%91.html

思路

递归进行处理，每次先将当前节点子树中的节点进行递归翻转。然后将当前节点的left指向当前的右子树，right指向当前的左子树，做翻转操作。

C++实现

/*** 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:TreeNode* invertTree(TreeNode* root) {doInvert(root);return root;}void doInvert(TreeNode* node){if(node == nullptr) return;doInvert(node->left);doInvert(node->right);TreeNode* leftTree = node->left;TreeNode* rightTree = node->right;node->left = rightTree;node->right = leftTree;}
};

101.对称二叉树

题目链接：101. 对称二叉树

给你一个二叉树的根节点 root ，检查它是否轴对称。

文章讲解/视频讲解：https://programmercarl.com/0101.%E5%AF%B9%E7%A7%B0%E4%BA%8C%E5%8F%89%E6%A0%91.html

思路

首先，如果root为空或者root没有左右子树，则说明对称。

如果root两棵树不全为空，或者都不为空，但是值不相等，则说明不对称。

否则进行递归处理，判断当前对应的两棵子树是否对称，判断的根据还是根据两棵子树是否为空、两棵子树的对称位置子树是否一致等。具体参见代码。

C++实现

/*** 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:bool isSymmetric(TreeNode* root) {if(root == nullptr) return true;if(root->left == nullptr && root->right == nullptr){return true;}else if(root->left != nullptr && root->right != nullptr && root->left->val == root->right->val){return doJudge(root->left, root->right);}else{return false;}}bool doJudge(TreeNode* leftPart, TreeNode* rightPart){if(leftPart == nullptr && rightPart == nullptr){return true;}else if(leftPart != nullptr && rightPart != nullptr && leftPart->val == rightPart->val){bool result = doJudge(leftPart->left, rightPart->right) && doJudge(leftPart->right, rightPart->left);return result;}else{return false;}}
};