代码随想录算法训练营29期Day16|LeetCode 104,559,111,222

发布时间:2024年01月13日

?文档讲解:二叉树的最大深度??二叉树的最小深度??完全二叉树的节点个数

104.二叉树的最大深度

题目链接:https://leetcode.cn/problems/maximum-depth-of-binary-tree/description/

思路:

? ? ? ? 求二叉树的深度,其实本质上还是遍历,需要我们找到叶子节点,统计叶子节点的深度即可。

? ? ? ? 因此我们就有多种思路,总结出来就是两种方法,一种是递归法,也就是深度优先搜索,借其进行前中后序遍历即可,这种比较好写,但时间复杂度高,因此本文不做过多阐述。第二种方法是迭代法,也就是广度优先搜索,通常借助队列来实现,下面解释思路。

? ? ? ? 在上一篇文章(Day15)的题目中,我们知道了层序遍历如何做,同时知道了每次同时加入队列或从队列中弹出的节点是同一层的,这样我们每处理一层的节点就把统计的深度加一,初始值为0,那么当我们处理到最后一层时,深度自然也就统计到最大值。

核心代码:

/**
 * 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:
    int maxDepth(TreeNode* root) {
        int depth=0;
        queue<TreeNode*> q;
        if(root) q.push(root);
        while(!q.empty()){
            depth++;
            TreeNode* cur;
            int n=q.size();
            while(n--){
                cur=q.front();
                q.pop();
                if(cur->left) q.push(cur->left);
                if(cur->right) q.push(cur->right);
            }
        }
        return depth;
    }
};

559.N叉树的最大深度

题目链接:https://leetcode.cn/problems/maximum-depth-of-n-ary-tree/submissions/494720068/

思路:

? ? ? ? N叉树求最大深度,和上一道题目是一模一样的原理。只不过我们在遍历每个节点的儿子时,不再是左右节点,而是一个vector数组,我们针对vector去遍历,判断是否为空加入队列即可,深度的判断逻辑则完全没有改变。本文不再赘述。

核心代码:

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    int maxDepth(Node* root) {
        queue<Node*> q;
        int depth=0;
        if(root) q.push(root);
        while(!q.empty()){
            depth++;
            int n=q.size();
            Node* cur;
            while(n--){
                cur=q.front();
                q.pop();
                int cnt=cur->children.size();
                for(int j=0;j<cnt;j++)
                  if(cur->children[j]) q.push(cur->children[j]);
            }
        }
        return depth;
    }
};

111.二叉树的最小深度

题目链接:https://leetcode.cn/problems/minimum-depth-of-binary-tree/description/

思路:

? ? ? ? 求二叉树的最小深度和最大深度,其实区别不大。

? ? ? ? 第一种方法,我们依旧可以利用递归来做,统计到叶子节点,就比较当前深度和记录的深度,取最小值即可。递归结束后的记录深度就是最小深度,输出即可。这样做的时间复杂度无法保证,基本会高,这种写法也简单易懂,就不再过多解释了。

? ? ? ? 第二种方法,用迭代法来做,就仿照上面的104或者559的求最大深度去做就行。那么在做之前,我们首先要知道,最小深度是什么。深度是针对叶子节点来说的,每个叶子节点都有对应深度,最小深度,肯定就是最靠近根节点的叶子节点的深度。那么叶子节点又是什么呢?是没有儿子的节点。了解上述问题,我们就可以解决这道题了。

? ? ? ? 我们依旧采用层序遍历的方式,借助队列来维护。每处理一层的节点,就把深度加一。处理每层的每个节点时,我们会判断它是否有左右儿子,有则加入队列,等待在下层进行处理,如果一个儿子都没有,那么证明它是叶子节点,而且是层数最靠根节点的叶子节点,那么它的深度即我们当前统计到的深度,就是该二叉树的最小深度,我们结束遍历输出这个深度即可。

核心代码:

/**
 * 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:
    int minDepth(TreeNode* root) {
        int depth=0;
        queue<TreeNode*> q;
        if(root) q.push(root);
        bool flag=false;
        while(!q.empty()){
            depth++;
            TreeNode* cur;
            int n=q.size();
            while(n--){
                cur=q.front();
                q.pop();
                if(cur->left) q.push(cur->left);
                if(cur->right) q.push(cur->right);
                if(cur->left==NULL&&cur->right==NULL) flag=true;
                if(flag) break;
            }
            if(flag) break;
        }
        return depth;
    }
};

222.完全二叉树的节点个数

题目链接:https://leetcode.cn/problems/count-complete-tree-nodes/description/

思路:

? ? ? ? 这题我们直接层序遍历,统计节点个数即可。这个方法不论是不是完全二叉树都能做,甚至是N叉树也能做,稍微改下写法就可以。时间复杂度为O(N),也完全可以接受。

核心代码:

/**
 * 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:
    int countNodes(TreeNode* root) {
        queue<TreeNode*> q;
        int ans=0;
        if(root) q.push(root);
        while(!q.empty()){
            int n=q.size();
            TreeNode* cur;
            while(n--){
                cur=q.front();
                q.pop();
                ans++;
                if(cur->left) q.push(cur->left);
                if(cur->right) q.push(cur->right);
            }
        }
        return ans;
    }
};

今日总结

????????今日学习时长3h,题目不算难,尤其有两道昨天就做了。

? ? ? ? 感冒好多了,下午接着看论文准备选题开题。

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