day15二叉树part02 | 层序遍历 10 226.翻转二叉树 101.对称二叉树 2

本文主要是介绍day15二叉树part02 | 层序遍历 10 226.翻转二叉树 101.对称二叉树 2，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

层序遍历 10


class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {queue<TreeNode*> que;;if (root == nullptr) return {};vector<vector<int>> result;// 根节点入队que.push(root);// 如果队列不为空while (!que.empty()){// 这里的size一定要用个变量保存一下// 因为有新的节点入队，队列的size是会一直变的int size = que.size();vector<int> vec;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;}
};

107. 二叉树的层序遍历 II
给你二叉树的根节点 root ，返回其节点值自底向上的层序遍历。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

class Solution {
public:vector<vector<int>> levelOrderBottom(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;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);}reverse(result.begin(), result.end());return result;}
};

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

class Solution {
public:vector<int> rightSideView(TreeNode* root) {queue<TreeNode*> que;;if (root == nullptr) return {};vector<int> result;// 根节点入队que.push(root);// 如果队列不为空while (!que.empty()){// 这里的size一定要用个变量保存一下// 因为有新的节点入队，队列的size是会一直变的int size = que.size();for (int i = 0; i < size; i++) {// 出队TreeNode* node = que.front();que.pop();// 保存当前节点的值if (i == size - 1)result.push_back(node->val);// 如果左右子树不为空，那么依次进队if (node->left) que.push(node->left);if (node->right) que.push(node->right);}}return result;}
};

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


class Solution {
public:vector<double> averageOfLevels(TreeNode* root) {queue<TreeNode*> que;;if (root == nullptr) return {};vector<double> result;// 根节点入队que.push(root);// 如果队列不为空while (!que.empty()){// 这里的size一定要用个变量保存一下// 因为有新的节点入队，队列的size是会一直变的int size = que.size();vector<int> vec;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);}double sumValue = accumulate(vec.begin(), vec.end(), 0.0);result.push_back(sumValue / vec.size());}return result;}
};

429. N 叉树的层序遍历
给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。
树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。


class Solution {
public:vector<vector<int>> levelOrder(Node* root) {queue<Node*> que;;if (root == nullptr) return {};vector<vector<int>> result;// 根节点入队que.push(root);// 如果队列不为空while (!que.empty()){// 这里的size一定要用个变量保存一下// 因为有新的节点入队，队列的size是会一直变的int size = que.size();vector<int> vec;for (int i = 0; i < size; i++) {// 出队Node* node = que.front();que.pop();// 保存当前节点的值vec.push_back(node->val);// 如果左右子树不为空，那么依次进队for (int i = 0; i < (node->children).size(); i++) {if ((node->children)[i] != nullptr) que.push((node->children)[i]);}}result.push_back(vec);}return result; }
};

题目链接/文章讲解/视频讲解：https://programmercarl.com/0102.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%B1%82%E5%BA%8F%E9%81%8D%E5%8E%86.html

116. 填充每个节点的下一个右侧节点指针
这题第一次理解不是很好

class Solution {
public:Node* connect(Node* root) {queue<Node*> que;if (root != nullptr) que.push(root);while (!que.empty()){int size = que.size();Node *node, *prenode;for (int i = 0; i < size; i++) {if (i == 0) { prenode = que.front();que.pop();node = prenode;} else {node = que.front();que.pop();prenode->next = node;prenode = prenode->next;}if (node->left) que.push(node->left);if (node->right) que.push(node->right);}prenode->next = nullptr;}return root;}
};

104. 二叉树的最大深度

class Solution {
public:int maxDepth(TreeNode* root) {queue<TreeNode*> que;int length = 0;if (root != nullptr) que.push(root);while (!que.empty()){int size = que.size();length++;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);}}return length;}
};

111. 二叉树的最小深度


class Solution {
public:int minDepth(TreeNode* root) {queue<TreeNode*> que;int length = 0;if (root != nullptr) que.push(root);while (!que.empty()){int size = que.size();length++;for (int i = 0; i < size; i++){TreeNode* node = que.front();que.pop();if (!node->left && !node->right)return length;if (node->left) que.push(node->left);if (node->right) que.push(node->right);}}return length;}
};

226.翻转二叉树

递归法

class Solution {
public:void traivl(TreeNode* root) {if (root != nullptr) {swap(root->left, root->right);if (root->left) invertTree(root->left);if (root->right) invertTree(root->right);}}TreeNode* invertTree(TreeNode* root) {if (root != nullptr) {traivl(root);}return root;}
};

迭代法

class Solution {
public:TreeNode* invertTree(TreeNode* root) {stack<TreeNode*> st;if (root != nullptr) st.push(root);while (!st.empty()){TreeNode* node = st.top();st.pop();swap(node->left, node->right);if (node->left) st.push(node->left);if (node->right) st.push(node->right);}return root;}
};

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

101.对称二叉树 2

class Solution {
public:bool Judgeroot(TreeNode* left, TreeNode* right) {// 确定终止条件// 1.左为空，右不为空// 2.左不为空,右为空// 3.左右都为空// 4.左右都不为空,但是不相等if (!left && right) return false;else if (left && !right) return false;else if (!left && !right) return true;else if (left->val != right->val) return false;// 这里就剩下左右不为空且相等的情况// 只能用后序遍历，因为只有这样才能将左右孩子的信息返回到上层// 比较左子树的左节点和右子树的右节点，这是比较外侧bool isLeft = Judgeroot(left->left, right->right);// 比较左子树的右节点和右子树的左节点，这是比较内侧bool isRight = Judgeroot(left->right, right->left);return isLeft && isRight;}bool isSymmetric(TreeNode* root) {// return Judgeroot(root->left, root->right);}
};