二叉树的层序遍历
题目链接：二叉树的层序遍历
题目描述：给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点
```
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
```
思路
学会二叉树的层序遍历，可以一口气打完以下十题：
102.二叉树的层序遍历
107.二叉树的层次遍历II
199.二叉树的右视图
637.二叉树的层平均值
429.N叉树的层序遍历
515.在每个树行中找最大值
116.填充每个节点的下一个右侧节点指针
117.填充每个节点的下一个右侧节点指针II
104.二叉树的最大深度
111.二叉树的最小深度
层序遍历一个二叉树，即从左到右一层一层遍历，重点是需要借助一个辅助数据结构---队列来实现
队列先进先出，符合一层一层遍历的逻辑，而栈呢，是适用模拟深度优先遍历也就是递归的逻辑
代码如下：作为二叉树层序遍历的模板，打十个
层次遍历实现：
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root){
queue<TreeNode> que;//定义一个队列来存取元素
if(root != NULL) que.push(root);//判断跟节点不为空
开始遍历二叉树
while(!que.empty()){
size = que.size();
vector<int> vec;//定义数组
开始遍历队列dangqian层的元素
while(size--){
// 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的
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;
}
小总结
本轮只是先解决层次遍历的大致解决思路及代码实现，第二轮深入各项题目进而做到打十个！！！
226.翻转二叉树
题目链接：226.翻转二叉树
题目描述：翻转一棵二叉树
```
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]
```
思路
什么是反转呢？
注意只要把每一个节点的左右孩子翻转一下，即可达到整体翻转的效果
这道题目使用前序和后序都是可以的，唯独中序遍历不方便，应为中序遍历会把某些节点的左右孩子翻转了两次
递归法--代码
递归三部曲：
1、确定递归函数的参数以及返回值
TreeNode* invertTree(TreeNode* root)
2、确定终止条件
if (root == NULL) return root;
3、确定单层递归的逻辑
swap(root->left, root->right);
invertTree(root->left);
invertTree(root->right);
代码实现：
翻转二叉树
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {递归的第一步：确定返回条件
if( root == NULL) return root;//di er bu
swap(root->left, root->right);//jiao huan (disanbu)中
inverTree(root->left);//xiang zuo bian li 左
inverTree(root->right);//右
return root;
}
迭代法--代码
即把递归用栈的方式模拟出来：
class Solution {
public:
TreeNode* invertTree(TreeNode* 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;
}
};
小总结
当然本题还有前中后序迭代方式的同意写法，以及层序遍历（广度优先遍历）也可以解决。尚未涉猎。
101. 对称二叉树
题目链接：101. 对称二叉树
题目描述：给定一个二叉树，检查它是否是镜像对称的
思路
首先想清楚，判断对称二叉树要比较的是哪两个节点，要比较的可不是左右节点！
对于二叉树是否对称，要比较的是根节点的左子树与右子树是不是相互翻转的，理解这一点就知道了其实我们要比较的是两个树（这两个树是根节点的左右子树），所以在递归遍历的过程中，也是要同时遍历两棵树。
**正是因为要遍历两棵树而且要比较内侧和外侧节点，所以准确的来说是一个树的遍历顺序是左右中，一个树的遍历顺序是右左中。
但都可以理解算是后序遍历，尽管已经不是严格上在一个树上进行遍历的后序遍历了。**
递归法--
- 确定递归函数的参数和返回值
bool compare(TreeNode* left, TreeNode* right) - 确定终止条件
节点为空的情况有：（注意我们比较的其实不是左孩子和右孩子，所以如下我称之为左节点右节点）
左节点为空，右节点不为空，不对称，return false
左不为空，右为空，不对称 return false
左右都为空，对称，返回true
此时已经排除掉了节点为空的情况，那么剩下的就是左右节点不为空：
左右都不为空，比较节点数值，不相同就return false
if (left == NULL && right != NULL) return false;
else if (left != NULL && right == NULL) return false;
else if (left == NULL && right == NULL) return true;
else if (left->val != right->val) return false;
- 确定单层递归的逻辑
比较二叉树外侧是否对称：传入的是左节点的左孩子，右节点的右孩子。
比较内测是否对称，传入左节点的右孩子，右节点的左孩子。
如果左右都对称就返回true ，有一侧不对称就返回false 。
bool outside = compare(left->left, right->right); // 左子树：左、 右子树：右
bool inside = compare(left->right, right->left); // 左子树：右、 右子树：左
bool isSame = outside && inside; // 左子树：中、 右子树：中（逻辑处理）
return isSame;
C++整体代码如下：
对称二叉树
class Solution {
public:
bool compare(TreeNode* left, TreeNode* right){ //定义函数参数，传入左右子树
//yixia是第二部 条件
if(left ==NULL && right != null) fasle;
else if (left != NULL && right == NULL) return false;
else if (left == NULL && right == NULL) return true;
else if(left->val != right->val ) return false;
// 比较外侧节点：
bool outside = compare(left->left, right->right);
bool inside = compare(left->right, right->left);//比较内测节点
// 内外都是相等才返回true
bool result = outside && inside;
return result;
}
bool isSymmetric(TreeNode* root) {
if (root == NULL) return true;
return compare(root->left, root->right);
}}
小总结
这道题目我们也可以使用迭代法，在迭代法中需要使用了队列，需要注意的是这不是层序遍历，而且仅仅通过一个容器来成对的存放我们要比较的元素，知道这一本质之后就发现，用队列，用栈，甚至用数组，都是可以的。---尚未涉猎1！！
标签：right,15,随想录,遍历,二叉树,root,节点,left From： https://www.cnblogs.com/lijian-allan/p/17232026.html