代码随想录算法训练营第十五天 |二叉树层序遍历（10道题目）、226.翻转二叉树、101. 对称二叉树

二叉树的层序遍历

讲解里提供了两个思路，一个是利用队列queue，另一个是使用递归，个人更喜欢利用队列实现，感觉这个方式逻辑更清晰，而且在做其余的有关二叉树层序遍历的题目时，用这个实现方式当作基础模板也很好改写出来。 自己才写了几遍就已经很熟悉了。

题目链接： leetcode 102.二叉树的层序遍历

文章讲解：代码随想录二叉树的层序遍历讲解

视频讲解：讲透二叉树的层序遍历 | 广度优先搜索 | LeetCode：102.二叉树的层序遍历

利用队列实现层序遍历：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        //使用队列
        queue<TreeNode*> que;
        //结果
        vector<vector<int>> result;
        //初始化
        if (root != nullptr) {
            que.push(root);
        }
        while (!que.empty()) {
            int n = que.size();
            vector<int> vec;
            for (int i = 0; i < n; i++) {
                TreeNode* cur = que.front();
                que.pop();
                vec.push_back(cur -> val);
                if (cur -> left) que.push(cur -> left);
                if (cur -> right) que.push(cur -> right);
            }
            result.push_back(vec);
        }
        return result;
    }
};

题目链接：leetcode 226.翻转二叉树

文章讲解：代码随想录226.翻转二叉树讲解

视频讲解：听说一位巨佬面Google被拒了，因为没写出翻转二叉树 | LeetCode：226.翻转二叉树

题目：
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
想法：
感觉讲解里写的反而有些复杂了，可能出于严谨的考虑。这里只记录自己最后总结的思路。关键思想在于翻转如何实现，其实只要把每个节点的左右孩子翻转一下就可以了， 用swap函数翻转两个孩子指针即可，这里我选用了层序遍历。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        //思路：利用层序遍历，对每个节点的左右子节点翻转一下
        queue<TreeNode*> que;
        if (root != nullptr) que.push(root);
        while (!que.empty()) {
            int size = que.size();
            for (int i = 0; i < size; i++) {
                TreeNode* cur = que.front();
                que.pop();
                swap(cur -> left, cur -> right);
                if (cur -> left) que.push(cur -> left);
                if (cur -> right) que.push(cur -> right);
            }
        }
        return root;
    }
};

题目链接： leetcode 101. 对称二叉树

文章讲解：代码随想录101. 对称二叉树讲解

视频讲解：同时操作两个二叉树 | LeetCode：101. 对称二叉树

题目：
给你一个二叉树的根节点 root ， 检查它是否轴对称。
想法：
同样感觉讲解里写的反而有些复杂了。。。这里只记录自己最后总结的思路。主要是感觉提及只能用后序遍历这个点没有必要，我有了解到回溯算法，但是我自己还没有深入学习过，所以也可能是我目前知识体系不完善导致我不能很好地理解这种总结。这里我暂时认为就是递归的思路，关键思想在于如何判断轴对称，其实判断轴对称我们应该始终手动提供两侧对应位置的节点（也就是讲解中说的内侧还是外侧，因为是二叉树，所以要么同时提供内侧，要么同时提供外侧），然后递归的结束条件需要仔细考虑一下，注意两侧都为空时返回true，然后处理如果两侧值都相等，如何向下进行递归，递归就是判断下一层的子节点是否还对称，如果都对称，回溯到这一层最终就要返回true。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    //实现判断两个子树是否可以翻转的函数
    bool compare(TreeNode* left, TreeNode* right) {
        if (left == nullptr && right == nullptr) return true;
        else if (left == nullptr && right != nullptr) return false;
        else if (right ==nullptr && left != nullptr) return false;
        else if (left -> val != right -> val) return false;
        bool outside = compare(left -> left, right -> right);
        bool inside = compare(left -> right, right -> left);
        return outside && inside;
    }

    bool isSymmetric(TreeNode* root) {
        return compare(root -> left, root -> right);
    }
};