今天写了十几道二叉树的题目，算下来应该都是比较简单的题。但是对称二叉树这题我真的理解了很久。下面不做具体说明，仅记录代码作为日后的回顾。
102 二叉树的层序遍历
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
queue<TreeNode*> que;
if(root) que.push(root);
while(!que.empty())
{
int size = que.size();
vector<int> vec;
for(int i = 0;i<size;i++)
{
TreeNode* p = que.front();
que.pop();
vec.push_back(p->val);
if(p->left) que.push(p->left);
if(p->right) que.push(p->right);
}
res.push_back(vec);
}
return res;
}
};
class Solution {
public:
vector<vector<int>> levelOrderBottom(TreeNode* root) {
vector<vector<int>> res;
queue<TreeNode*> que;
if(root) que.push(root);
while(!que.empty())
{
int size = que.size();
vector<int> vec;
for(int i = 0;i<size;i++)
{
TreeNode* p = que.front();
que.pop();
vec.push_back(p->val);
if(p->left) que.push(p->left);
if(p->right) que.push(p->right);
}
res.push_back(vec);
}
reverse(res.begin(),res.end());
return res;
}
};
class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
vector<vector<int>> res;
queue<TreeNode*> que;
if(root) que.push(root);
while(!que.empty())
{
int size = que.size();
vector<int> vec;
for(int i = 0;i<size;i++)
{
TreeNode* p = que.front();
que.pop();
vec.push_back(p->val);
if(p->left) que.push(p->left);
if(p->right) que.push(p->right);
}
res.push_back(vec);
}
vector<int> ans;
for(auto vec : res)
{
ans.push_back(vec[vec.size()-1]);
}
return ans;
}
};
class Solution {
public:
vector<double> averageOfLevels(TreeNode* root) {
vector<vector<int>> res;
queue<TreeNode*> que;
if(root) que.push(root);
while(!que.empty())
{
int size = que.size();
vector<int> vec;
for(int i = 0;i<size;i++)
{
TreeNode* p = que.front();
que.pop();
vec.push_back(p->val);
if(p->left) que.push(p->left);
if(p->right) que.push(p->right);
}
res.push_back(vec);
}
vector<double> vecd;
for(auto vec : res)
{
double sum = 0;
for(auto i : vec)
{
sum += i;
}
double avg = sum/vec.size();
vecd.push_back(avg);
}
return vecd;
}
};
class Solution {
public:
vector<vector<int>> levelOrder(Node* root) {
vector<vector<int>> res;
queue<Node*> que;
if(root) que.push(root);
while(!que.empty())
{
int size = que.size();
vector<int> vec;
for(int i = 0;i<size;i++)
{
Node* p = que.front();
que.pop();
vec.push_back(p->val);
// 几叉树就用一个for循环遍历所有的分枝，其余和二叉树遍历一样
for(int i = 0;i<p->children.size();i++)
{
if(p->children[i]) que.push(p->children[i]);
}
}
res.push_back(vec);
}
return res;
}
};
class Solution {
public:
vector<int> largestValues(TreeNode* root) {
vector<vector<int>> res;
queue<TreeNode*> que;
if(root) que.push(root);
while(!que.empty())
{
int size = que.size();
vector<int> vec;
for(int i = 0;i<size;i++)
{
TreeNode* p = que.front();
que.pop();
vec.push_back(p->val);
if(p->left) que.push(p->left);
if(p->right) que.push(p->right);
}
res.push_back(vec);
}
vector<int> ans;
for(vector<int> vec : res)
{
int Max = INT_MIN;
for(int i = 0;i<vec.size();i++)
{
if(vec[i] > Max)
Max = vec[i];
}
ans.push_back(Max);
}
return ans;
}
};
class Solution {
public:
Node* connect(Node* root) {
vector<vector<Node*>> vecs;
queue<Node*> que;
if(root) que.push(root);
while(!que.empty())
{
int size = que.size();
vector<Node*> vec;
for(int i = 0;i<size;i++)
{
Node* tmp = que.front();
que.pop();
vec.push_back(tmp);
if(tmp->left) que.push(tmp->left);
if(tmp->right) que.push(tmp->right);
}
vecs.push_back(vec);
}
for(auto vec : vecs)
{
for(int i = 0;i<vec.size()-1;i++)
{
vec[i]->next = vec[i+1];
}
}
return root;
}
};
class Solution {
public:
int maxDepth(TreeNode* root) {
// 我靠，直接懵的
if(root == nullptr)
return 0;
int left = maxDepth(root->left);
int right = maxDepth(root->right);
return left>right?left+1:right+1;
}
};
class Solution {
public:
int minDepth(TreeNode* root) {
if(root == nullptr)
return 0;
if(root->left == nullptr && root->right == nullptr)
return 1;
int min_depth = INT_MAX;
if(root->left != nullptr)
{
min_depth = min(minDepth(root->left),min_depth);
}
if(root->right != nullptr)
{
min_depth = min(minDepth(root->right),min_depth);
}
return min_depth+1;
}
};
吐槽一句，怎么二叉树的最小深度那么难写
226. 翻转二叉树
罗列了四种写法，两种递归，两种迭代
写的比较详细的一集，属于是很好记，但是比较难写对的一集
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
// 递归写法 先序
if(root == nullptr)
return root;
swap(root->left,root->right);
invertTree(root->left);
invertTree(root->right);
return root;
// 递归写法 后序
if(root == nullptr)
return root;
invertTree(root->left);
invertTree(root->right);
swap(root->left,root->right);
return root;
// 非递归写法 前序
if (root == NULL) return root;
stack<TreeNode*> st;
st.push(root);
while(!st.empty()) {
TreeNode* node = st.top(); // 中
st.pop();
swap(node->left, node->right);
if(node->right) st.push(node->right); // 右
if(node->left) st.push(node->left); // 左
}
return root;
// 层序遍历
queue<TreeNode*> que;
if(root == nullptr)
return root;
que.push(root);
while(!que.empty())
{
int size = que.size();
for(int i = 0;i<size;i++)
{
TreeNode* tmp = que.front();
que.pop();
swap(tmp->left,tmp->right);
if(tmp->left) que.push(tmp->left);
if(tmp->right) que.push(tmp->right);
}
}
return root;
}
};
class Solution {
public:
// 同时遍历两棵树，后序遍历，左子树是左右中，右子树是右左中
bool compare(TreeNode* left,TreeNode* right)
{
if(left == nullptr && right != nullptr)
return false;
else if(left != nullptr&& right == nullptr)
return false;
else if(left == nullptr && right == nullptr)
return true;
else if(left->val != right->val)
return false;
// 所有情况判定完成就剩下左右孩子存在且值相等的情况
else
{
// 必须要内侧和外侧都对称才返回true，在判定过程中只要有一次错误，后续返回的结果必为false
bool outside = compare(left->left,right->right);
bool inside = compare(left->right,right->left);
if(outside && inside)
return true;
else
return false;
}
}
bool isSymmetric(TreeNode* root) {
if(root == nullptr)
return true;
return compare(root->left,root->right);
}
};
思路：属实是被简单题蒙蔽了双眼，我只是一个傻瓜。开始想的是层序遍历，然后存储null节点，判断每行是否可以构成回文序列，思路可行，代码不太好写；然后就是两个函数递归遍历树的左右子树，左边左右中，右边右左中，遍历的序列分别存储进入vector容器中，然后直接比较vector是否相等，但是也存在同样的痛点，左右子树每行节点值以及个数相等，但是顺序不等，还有五十多个用例没有通过。最后看了卡尔的方法，不得不说还是近似的思路，不过这个是左右同时开工，左子树左边一路走到黑，右子树右边一路走到黑，然后左边走向右边，右边走向左边，彼此交叉，一遇到不对的结果就不对了。但是啊，递归啊递归，我真的是要了老命了，怎么递归那么难理解，而且电脑的栈也太强大了，不仅存储代码运行的变量，还得存储这一遍运行到的行数，关键是不同的参数以及局部变量每一层都在改变。不得不说当初在写汇编的时候对栈的理解狭隘了。
每天坚持吧，能写完就是胜利。
