文章目录
层序遍历
我们使用队列模拟二叉树的层序遍历。
相关题目
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
queue<TreeNode*> que;
vector<vector<int>> result;
if (root != nullptr) que.push(root);
while (!que.empty()) {
int size = que.size();
vector<int>vec;
while (size--) {
TreeNode* cur = que.front();
que.pop();
vec.push_back(cur->val);
if (cur->left) que.push(cur->left);
if (cur->right) que.push(cur->right);
}
result.push_back(vec);
}
return result;
}
};
在层序遍历的基础上翻转 result 数组即可
class Solution {
public:
vector<vector<int>> levelOrderBottom(TreeNode* root) {
queue<TreeNode*> que;
vector<vector<int>> result;
if (root != nullptr) que.push(root);
while (!que.empty()) {
int size = que.size();
vector<int>vec;
while (size--) {
TreeNode* cur = que.front();
que.pop();
vec.push_back(cur->val);
if (cur->left) que.push(cur->left);
if (cur->right) que.push(cur->right);
}
result.push_back(vec);
}
reverse(result.begin(), result.end());
return result;
}
};
class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
queue<TreeNode*> que;
vector<int> result;
if (root != nullptr) que.push(root);
while (!que.empty()) {
int size = que.size();
while (size--) {
TreeNode* cur = que.front();
que.pop();
if (size == 0) result.push_back(cur->val);
if (cur->left) que.push(cur->left);
if (cur->right) que.push(cur->right);
}
}
return result;
}
};
class Solution {
public:
double average(vector<double> vec) {
double sum = 0;
double avg = 0;
for (int i = 0; i < vec.size(); i++) {
sum += vec[i];
}
avg = sum / vec.size();
return avg;
}
vector<double> averageOfLevels(TreeNode* root) {
queue<TreeNode*> que;
vector<double> result;
if (root != nullptr) que.push(root);
while (!que.empty()) {
int size = que.size();
vector<double>vec;
while (size--) {
TreeNode* cur = que.front();
que.pop();
vec.push_back(cur->val);
if (cur->left) que.push(cur->left);
if (cur->right) que.push(cur->right);
}
result.push_back(average(vec));
}
return result;
}
};
class Solution {
public:
vector<vector<int>> levelOrder(Node* root) {
queue<Node*> que;
vector<vector<int>> result;
if (root != nullptr) que.push(root);
while (!que.empty()) {
int size = que.size();
vector<int>vec;
while (size--) {
Node* cur = que.front();
que.pop();
vec.push_back(cur->val);
for (int i = 0; i < cur->children.size(); i++) {
if (cur->children[i] != nullptr) que.push(cur->children[i]);
}
}
result.push_back(vec);
}
return result;
}
};
class Solution {
public:
int getLargest(vector<int> vec) {
int large = vec[0];
for (int i = 1; i < vec.size(); i++) {
if (vec[i] > large) large = vec[i];
}
return large;
}
vector<int> largestValues(TreeNode* root) {
queue<TreeNode*> que;
vector<int> result;
if (root != nullptr) que.push(root);
while (!que.empty()) {
int size = que.size();
vector<int>vec;
while (size--) {
TreeNode* cur = que.front();
que.pop();
vec.push_back(cur->val);
if (cur->left) que.push(cur->left);
if (cur->right) que.push(cur->right);
}
result.push_back(getLargest(vec));
}
return result;
}
};
class Solution {
public:
Node* connect(Node* root) {
if (root == nullptr) return nullptr;
queue<Node*> queue;
queue.push(root);
while (!queue.empty()) {
int size = queue.size();
for (int i = 0; i < size; ++i) {
Node* node = queue.front();
queue.pop();
if (i < size - 1) {
node->next = queue.front();
}
else {
node->next = nullptr;
}
if (node->left) queue.push(node->left);
if (node->right) queue.push(node->right);
}
}
return root;
}
};
Leetcode 226-翻转二叉树
题目描述
https://leetcode.cn/problems/invert-binary-tree/description/
解题思路
我们使用前序遍历解决这道问题：
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (root == NULL) return root;
swap(root->left, root->right);//中
invertTree(root->left);//左
invertTree(root->right);//右
return root;
}
};
Leetcode 101-对称二叉树
题目描述
https://leetcode.cn/problems/symmetric-tree/description/
解题思路
判断二叉树是否对称我们可以转化为判断中间节点的左右节点翻转后是否相等，在比较左右节点翻转时，我们需要分别比较外侧节点和内侧节点是否对称
由此可得以下代码：
class Solution {
public:
bool campare(TreeNode* left, TreeNode* right) {
//首先先判断当前的左右节点是否为空，进行剪枝
if (left == NULL && right == NULL) return true;
else if (left != NULL && right == NULL) return false;
else if (left == NULL && right != NULL) return false;
else if (left->val != right->val) return false;//如果左右节点不为空但值不相同
else {//如果左右节点不为空并且值相同，对其子节点进行进一步的判断
bool outside = campare(left->left, right->right);//比较外侧节点
bool inside = campare(left->right, right->left);//比较内侧节点
bool isSame = outside && inside;
return isSame;
}
}
bool isSymmetric(TreeNode* root) {
if (root == NULL) return true;
return campare(root->left, root->right);
}
};