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

发布时间:2023年12月27日

层序遍历

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

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;
        }
    }
};

文章来源:https://blog.csdn.net/weixin_43347688/article/details/135242782
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。