1.层序遍历

102. 二叉树的层序遍历

1.首先层序遍历是通过队列结构实现的

2.其实就是循环将每一层节点入队列，随后出队列将数据存储起来。通过出队列的节点，将其左右节点，也就是再把下一层的节点入队列。那么我们就能得到层序遍历的结果了

3.我实现这题用了一个队列存储节点，一个vector<TreeNode*>存储出队列节点，一个vector<int>存储一层的数据。

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> ret;if(root==nullptr)return ret;queue<TreeNode*> q;q.push(root);while(!q.empty()){vector<TreeNode*> tmp;while(!q.empty()){tmp.push_back(q.front());q.pop();}vector<int> v;for(auto& e:tmp){v.push_back(e->val);if(e->left)q.push(e->left);if(e->right)q.push(e->right);}ret.push_back(v);}return ret;}
};

2.翻转二叉树

226. 翻转二叉树

1.由于我们要在开始就需要把左右节点调换，之后往下递归。

2.所以我们使用的是前序遍历

那么传入的值其实就是根节点，返回值不需要所以未void

如果我们访问到的节点为空，那么递归结束

进行执行调换操作，我们只需要把左右节点相互交换即可

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

3.对称二叉树

101. 对称二叉树

1.需要判断是否对称，那么其实我们是不能使用前中序遍历的，因为这两个遍历方式，没能起到把所有的节点结果得到，就进行判断，这样并不能得到最后的结果

2.所以我们需要使用后续遍历

首先是传入的参数，其实我们要判断的就是一个节点的左右子树是否对称，所以我们传入的参数是左右节点；返回值由于需要判断是否为对称，因此传出一个bool

结束条件有三种：

一、左子树为空，右子树不为空或者左子树不为空，右子树为空返回false

二、左子树为空，右子树为空返回true

三、左子树不为空，右子树不为空，且两个值不相同，返回false

最后的执行操作就是将左右节点递归返回的值进行AND，最后返回就是对称与否的结果

3.注意，在写条件判断时，一定要先判断有无节点的条件，在判断是否相等，这样就不会出现非法访问的操作了

class Solution {
public:bool _isSymmetricR(TreeNode* left,TreeNode* right){if(!left&&right||left&&!right)return false;if(left==nullptr&&right==nullptr)return true;if(left->val!=right->val)return false;return _isSymmetricR(left->left,right->right)&&_isSymmetricR(left->right,right->left);}bool isSymmetric(TreeNode* root) {return _isSymmetricR(root,root);}
};