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

层序遍历

层序遍历，就是从左到右一层层的去遍历二叉树，这种遍历方式就是图论中的广度优先遍历。实现广度优先遍历，需要借助队列这个数据结构来实现。层序遍历的模板如下：

class Solution{
 public:
    vector<vector<int>> levelOrder(TreeNode* root){
        queue<TreeNode*> que;
        if(root != nullptr) 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;
    }
};

递归法的模板如下：

class Solution{
public:
    void order(TreeNode* cur, vector<vector<int>>& result, int depth){
        if(cur == nullptr) return;
        if(result.size() == depth) result.push_back(vector<int>());
        result[depth].push_back(cur->val);
        order(cur->left, result, depth + 1);
        order(cur->right, result, depth + 1);
    }
    vector<vector<int>> levelOrder(TreeNode* root){
        vector<vector<int>> result;
        int depth = 0;
        order(root, result, depth);
        return result;
    }
};

利用模板，可以一连打十道题，如下：

102. 二叉树的层序遍历

思路：标准的层序遍历，利用上述的版子就可以解答

107. 二叉树的层序遍历 II

思路：先做层序遍历，然后将结果反转

199. 二叉树的右视图

思路：进行层次遍历，每次将每层的最后一个节点的值添加到结果中

637. 二叉树的层平均值

思路：进行层次遍历，然后对每层的结果做平均，注意每个节点的数值是否越过int的边界

429. N 叉树的层序遍历

思路：和二叉树的层序遍历类似，采用队列作为容器来实现

515. 在每个树行中找最大值

思路：用层序方式进行遍历，然后找出每层中的最大值，添加入结果

116. 填充每个节点的下一个右侧节点指针

思路：进行层序遍历，然后在遍历的过程中不断地将每层的前一个节点指向后一个节点

117. 填充每个节点的下一个右侧节点指针 II

思路：这题和上一题一模一样，进行层序遍历，然后把前一个节点指向后一个节点

104. 二叉树的最大深度

思路：可以采用层序遍历来解决，每一层记一次数，总数就是二叉树的最大深度

111. 二叉树的最小深度

思路：进行层次遍历，如果在遍历时，发现当前有一个节点既没有左子树又没有右子树，则当前节点的深度为二叉树的最小深度

226.翻转二叉树

题目链接：226. 翻转二叉树
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

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

思路

递归进行处理，每次先将当前节点子树中的节点进行递归翻转。然后将当前节点的left指向当前的右子树，right指向当前的左子树，做翻转操作。

C++实现

/**
 * 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) {
        doInvert(root);
        return root;
    }

    void doInvert(TreeNode* node){
        if(node == nullptr) return;

        doInvert(node->left);
        doInvert(node->right);

        TreeNode* leftTree = node->left;
        TreeNode* rightTree = node->right;
        node->left = rightTree;
        node->right = leftTree;
    }
};

101.对称二叉树

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

给你一个二叉树的根节点 root ， 检查它是否轴对称。

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

思路

首先，如果root为空或者root没有左右子树，则说明对称。

如果root两棵树不全为空，或者都不为空，但是值不相等，则说明不对称。

否则进行递归处理，判断当前对应的两棵子树是否对称，判断的根据还是根据两棵子树是否为空、两棵子树的对称位置子树是否一致等。具体参见代码。

C++实现

/**
 * 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 isSymmetric(TreeNode* root) {
        if(root == nullptr) return true;

        if(root->left == nullptr && root->right == nullptr){
            return true;
        }
        else if(root->left != nullptr && root->right != nullptr && root->left->val == root->right->val){
            return doJudge(root->left, root->right);
        }
        else{
            return false;
        }
    }

    bool doJudge(TreeNode* leftPart, TreeNode* rightPart){
        if(leftPart == nullptr && rightPart == nullptr){
            return true;
        }
        else if(leftPart != nullptr && rightPart != nullptr && leftPart->val == rightPart->val){
            bool result = doJudge(leftPart->left, rightPart->right) && doJudge(leftPart->right, rightPart->left);
            return result;
        }
        else{
            return false;
        }
    }
};