代码随想录算法训练营第十五天| 层序遍历 10 ，226.翻转二叉树 101.对称二叉树 2

层序遍历 

    卡哥建议：看完本篇可以一口气刷十道题，试一试， 层序遍历并不难，大家可以很快刷了十道题。

    题目链接/文章讲解/视频讲解：https://programmercarl.com/0102.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%B1%82%E5%BA%8F%E9%81%8D%E5%8E%86.html

    做题思路：

    层序遍历就是一层一层的遍历，从二叉树的第一层到最后一层。用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。而这种层序遍历方式就是图论中的广度优先遍历，只不过我们应用在二叉树上。使用队列实现二叉树广度优先遍历。

    我们每遍历一层的元素，就用队列去保存，然后用变量size记录下队列的大小，接下来把这一层元素弹出来，对下一层进行处理，比如把第一层的根节点弹出来后，再把第二层的根节点的左右孩子加入队列，再用size记录第二层元素个数。当弹出第二层的一个节点后，再把弹出的这个节点对应的左右孩子加入队列里，此时队列既有第二层的元素，又有第三层的元素，如果对队列弹出的元素数量不加以控制的话，怎么知道队列里哪些元素是第二层的，哪些是第三层，所以这里用size记录。我们在遍历完第二层的时候，同时把第二层每个节点的左右孩子也加入队列里了。

   层序遍历代码：

 1 vector<vector<int>> levelOrder(TreeNode* root) {
 2         queue<TreeNode*> que;
 3         if (root != NULL) que.push(root);
 4         vector<vector<int>> result;
 5         while (!que.empty()) {
 6             int size = que.size();
 7             vector<int> vec;
 8             // 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的
 9             for (int i = 0; i < size; i++) {
10                 TreeNode* node = que.front();
11                 que.pop();
12                 vec.push_back(node->val);
13                 if (node->left) que.push(node->left);
14                 if (node->right) que.push(node->right);
15             }
16             result.push_back(vec);
17         }
18         return result;

 226.翻转二叉树 （优先掌握递归） 

     卡哥建议：这道题目 一些做过的同学 理解的也不够深入，建议大家先看我的视频讲解，无论做过没做过，都会有很大收获。

    题目链接/文章讲解/视频讲解：https://programmercarl.com/0226.%E7%BF%BB%E8%BD%AC%E4%BA%8C%E5%8F%89%E6%A0%91.html

    做题思路：

      翻转画图理解的话，如上图，观察图发现，第一层的根节点没变，第二层的根节点的左右孩子互相交换了，同理，第三层的左右节点也交换了，翻转用c++的swap函数就行。注意理解的话，每个节点的左右孩子是不变的，不能变成其他节点的左右孩子，所以交换左右孩子的指针就能避免这点。

    这道题目使用前序遍历和后序遍历都可以，中序遍历不行，看卡哥视频讲解。递归思路看卡哥文章。

    本题前序遍历的递归法代码：

1 TreeNode* invertTree(TreeNode* root) {
2         if (root == NULL) return root;
3         swap(root->left, root->right);  // 中
4         invertTree(root->left);         // 左
5         invertTree(root->right);        // 右
6         return root;
7     }

101. 对称二叉树 （优先掌握递归）  

    卡哥建议：先看视频讲解，会更容易一些。 

   题目链接/文章讲解/视频讲解：https://programmercarl.com/0101.%E5%AF%B9%E7%A7%B0%E4%BA%8C%E5%8F%89%E6%A0%91.html

   做题思路：

   如果两个节点的元素值相同，那对称；如果4个节点的内侧节点的元素值相同，并且外侧节点的元素值相同，那对称。对于二叉树，可以理解为原来的树和翻转后的树对称，除了根节点为空对称外，就是看根节点的左右子树是否为相互翻转，看两个子树的里侧和外侧的元素是否相等。比较二叉树外侧是否对称：传入的是左节点的左孩子，右节点的右孩子。比较内侧是否对称，传入左节点的右孩子，右节点的左孩子。如果左右都对称就返回true ，有一侧不对称就返回false 。还要先排除不对称的情况，左节点为空，右节点不为空，不对称，return false；左不为空，右为空，不对称， return false；左右都不为空，比较节点数值，不相同就return false。还有一种情况一定对称，左右都为空，对称，返回true。

     本题遍历只能是“后序遍历”，因为我们要通过递归函数的返回值来判断两个子树的内侧节点和外侧节点是否相等，递归它是要通过比较底部左右孩子是否相等的信息返回给上一层。这一块看卡哥视频讲解更清楚。

    本题后序遍历的递归法代码：

 1 bool compare(TreeNode* left, TreeNode* right) {
 2         // 首先排除空节点的情况
 3         if (left == NULL && right != NULL) return false;
 4         else if (left != NULL && right == NULL) return false;
 5         else if (left == NULL && right == NULL) return true;
 6         // 排除了空节点，再排除数值不相同的情况
 7         else if (left->val != right->val) return false;
 8 
 9         // 此时就是：左右节点都不为空，且数值相同的情况
10         // 此时才做递归，做下一层的判断
11         bool outside = compare(left->left, right->right);   // 左子树：左、 右子树：右
12         bool inside = compare(left->right, right->left);    // 左子树：右、 右子树：左
13         bool isSame = outside && inside;                    // 左子树：中、 右子树：中 （逻辑处理）
14         return isSame;
15 
16     }
17     bool isSymmetric(TreeNode* root) {
18         if (root == NULL) return true;
19         return compare(root->left, root->right);
20     }