层序遍历
费劲巴力的写出来了迭代法的层序遍历。中心思想其实是懂的，只不过出现了各种小错误。
比如在首个root node那里我就push back了一遍结果，但是在forloop里面又来了一次。再比如在pre_size和cur_st_size那里，我没有将两个数的数值协调好，它俩大部分的时候应该是同步的。
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
queue<TreeNode*> que;
int cur_st_size = 0;
TreeNode* cur_node;
if(root == nullptr){
return res;
}
else{
que.push(root);
cur_st_size++;
}
while(!que.empty()){
vector<int> temp_res;
int pre_size = cur_st_size;
while((pre_size > 0)&&(!que.empty())){
TreeNode* temp_node = que.front();
if(temp_node->left != nullptr){
que.push(temp_node->left);
cur_st_size++;
}
if(temp_node->right != nullptr){
que.push(temp_node->right);
cur_st_size++;
}
temp_res.push_back(temp_node->val);
que.pop();
pre_size--;
cur_st_size--;
}
res.push_back(temp_res);
}
return res;
}
};
对比了一下Carl的答案。首先是他用了que.size(),而我没想到用这个，而是自己手动去计算队列的size。其次，他用了for loop来遍历每一层的节点，而我是用了两个parameter一步一步同步，我那种就麻烦了许多。
我不仅是库的使用不够熟练，代码的简洁度方面也仍需要改进。
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
queue<TreeNode*> que;
if (root != NULL) 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;
}
};
随后还做了几道和这道题相关的题目。我用的方法都是迭代法。看到之前自己写的都是递归，其实不是那么好理解。虽然说递归的代码很简洁。但是理解题目以及做出来才是最重要的。有一道题是“116.填充每个节点的下一个右侧节点指针”我没有做，我觉得应该找机会做一下。
翻转二叉树
这道题有点偷懒了，看了我自己之前写的答案。然后用递归再写出来一遍。
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;
}
};
对称二叉树
这道题本来之间刷过一遍，但是又忘了该怎么写了。本来想用迭代法再做一遍，结果发现好像不行。后来过了一遍Carl的递归法，才写出来。
另外，写的时候还犯了一个错误，必须先检查left和right两个是不是nullptr之后，才能对比left和right的值是不是一样的，要不容易触发空指针。
class Solution {
public:
bool compare(TreeNode* left, TreeNode* right){
if(left==nullptr && right!=nullptr) return false;
if(left!=nullptr && right==nullptr) return false;
if(left==nullptr && right==nullptr) return true;
if(left->val != right->val) return false;
bool outer_result = compare(left->left,right->right);
bool inner_result = compare(left->right,right->left);
return outer_result&&inner_result;
}
bool isSymmetric(TreeNode* root) {
if(root == nullptr) return false;
return compare(root->left,root->right);
}
};
看了下Carl的迭代法，发现道理是基本上一样的，他是把成对的treenode放到栈里再进行对比的，而不是像之前从左向右或从右向左。自己做了一遍，也是挺好理解的。
class Solution {
public:
bool isSymmetric(TreeNode* root) {
queue<TreeNode*> que;
que.push(root->left);
que.push(root->right);
while(!que.empty()){
TreeNode* left = que.front();
que.pop();
TreeNode* right = que.front();
que.pop();
if(!left && !right){
continue;
}
if(!left || !right || left->val!=right->val){
return false;
}
que.push(left->left);
que.push(right->right);
que.push(left->right);
que.push(right->left);
}
return true;
}
};
