首页 > 编程语言 >代码随想录算法训练营第十六天| 104.二叉树的最大深度 559.n叉树的最大深度 111.二叉树的最小深度 222.完全二叉树的节点个数

代码随想录算法训练营第十六天| 104.二叉树的最大深度 559.n叉树的最大深度 111.二叉树的最小深度 222.完全二叉树的节点个数

时间:2024-02-08 23:22:35浏览次数:27  
标签:node return int 随想录 二叉树 深度 NULL root

104.二叉树的最大深度  

题目链接:104. 二叉树的最大深度 - 力扣(LeetCode)n叉树也一样

思路:我的普通递归方法

class Solution {
public:
    int depth(TreeNode* node,int d){
        int l=0,r=0;
        if(node->left==NULL&&node->right==NULL) return d;
        if(node->left)l=depth(node->left,d+1);
        if(node->right)r=depth(node->right,d+1);
        return max(l,r);
    }
    int maxDepth(TreeNode* root) {
        if(root==NULL)return 0;
        return depth(root,1);
    }
};

真是太简洁了

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        return max(maxDepth(root->left), maxDepth(root->right)) + 1;
    }
};

作者:力扣官方题解
链接:https://leetcode.cn/problems/maximum-depth-of-binary-tree/solutions/349250/er-cha-shu-de-zui-da-shen-du-by-leetcode-solution/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

 

 111.二叉树的最小深度

题目链接:111. 二叉树的最小深度 - 力扣(LeetCode)

思路:显然本题和上一题思路不是很一致,因为根节点的子节点空缺和普通节点的子节点空缺是两种情况,这里参考官网做法。

错误做法:

class Solution {
public:
    int minDepth(TreeNode* root) {
        if(root==NULL)return 0;
        return min(minDepth(root->left),minDepth(root->right))+1;
    }
};

事实上,只有左右节点皆为空,才叫叶子节点。

class Solution {
public:
    int getDepth(TreeNode* node) {
        if (node == NULL) return 0;
        int leftDepth = getDepth(node->left);           // 左
        int rightDepth = getDepth(node->right);         // 右
                                                        // 中
        // 当一个左子树为空,右不为空,这时并不是最低点
        if (node->left == NULL && node->right != NULL) { 
            return 1 + rightDepth;
        }   
        // 当一个右子树为空,左不为空,这时并不是最低点
        if (node->left != NULL && node->right == NULL) { 
            return 1 + leftDepth;
        }
        int result = 1 + min(leftDepth, rightDepth);
        return result;
    }

    int minDepth(TreeNode* root) {
        return getDepth(root);
    }
};

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

题目链接:222. 完全二叉树的节点个数 - 力扣(LeetCode)

思路:自己根据第一题仿造出来的比较暴力的递归,没有利用完全二叉树的性质。

class Solution {
public:
    int countNodes(TreeNode* root) {
        if(root==NULL)return 0;
        return countNodes(root->left)+countNodes(root->right)+1;
    }
};

 

标签:node,return,int,随想录,二叉树,深度,NULL,root
From: https://www.cnblogs.com/Liubox/p/18012242

相关文章

  • (16/60)二叉树最大深度、最小深度、完全二叉树结点个数
    终于熬到了春节假~~有些手感了深度与高度深度是从根结点到叶结点的距离;高度是从叶结点到根结点的距离。深度从上往下(根为1);高度从下往上(叶为1)。二叉树最大深度leetcode:104.二叉树的最大深度后序递归法思路复杂度分析时间复杂度:O(N)。遍历了一遍。空间复杂度:和层数有关......
  • 005_二叉树
    1.用递归和非递归的方式实现二叉树的先序、中序、后序遍历先序遍历递归publicvoidpreOrderRecur(TreeNoderoot){if(root==null){return;}System.out.println(root.val+"");preOrderRecur(root.left);preOrderRecur(root.right);}......
  • 代码随想录 day44 零钱兑换 II 组合总和 Ⅳ
    零钱兑换II这里组合类问题用上了dp[j]=dp[j-nums[i]]这个递推式由于说了硬币可以用无数次也就是这是个完全背包问题这里先遍历物品再遍历背包就是算了组合数反过来就是算排列数组合总和Ⅳ这题就是组合类问题的排列数模板题......
  • 代码随想录 day43 最后一块石头的重量 II 目标和 一和零
    最后一块石头的重量II递推式和结果处理结果的意思是sum-target和target这两堆石头相撞目标和第一次见被薄纱这是组合类的dp递推一和零注意循环嵌套位置!这里是str外循环表示遍历物品里面的两层ij循环表示遍历背包容量这里是一个二维容量的背包......
  • (15/60)层序遍历、翻转二叉树、对称二叉树
    层序遍历leetcode:102.二叉树的层序遍历107.二叉树的层序遍历II199.二叉树的右视图637.二叉树的层平均值429.N叉树的层序遍历515.在每个树行中找最大值116.填充每个节点的下一个右侧节点指针104.二叉树的最大深度111.二叉树的最小深度102.二叉树的层序遍......
  • 代码随想录算法训练营第十五天| 层序遍历 10 226.翻转二叉树 101.对称二叉树 2
    层序遍历  102.二叉树的层序遍历-力扣(LeetCode)思路:结合了昨天学到的标记法,每当一层遍历完,向队列中添加一个NULL标记。遍历到NULL节点表示该层遍历完了,将结果存入结果集中。/***Definitionforabinarytreenode.*structTreeNode{*intval;*TreeNo......
  • P2585 [ZJOI2006] 三色二叉树
    原题链接总结1.要学会动态规划这种思维方式,即定义状态和状态之间的转移2.本题的难点在于如何将抽象的输入数据转换成树状结构处理和定义状态,这个定义状态让我想到了初中添加几何线,可能要多做题才能有感觉吧3.有一定模拟的部分,这一部分要细心\(Code\)#include<bits/stdc++.h>......
  • 树与图的深度优先遍历
    #include<iostream>#include<algorithm>#include<cstring>usingnamespacestd;constintN=100010,M=N*2;intn;inth[N],e[M],ne[M],idx;boolst[N];intans=N;voidadd(inta,intb){e[idx]=b,ne[idx]=h[......
  • (14/60)二叉树理论基础、递归遍历、迭代遍历、统一迭代
    二叉树理论基础分类满二叉树:只有度为0和度为2的结点,且度为0结点在同一层上(每一层的结点都是满的)。完全二叉树:除了底层外其他层结点都是满的(底层当然也可以是满的),且底层结点从左往右连续不断。二叉搜索树:树的每个结点满足:左子树所有结点值均小于根结点的值右子树所有......
  • 代码随想录 day42 背包问题 分割等和子集
    01背包leetcode没有原题这里是解法importjava.util.Arrays;publicclassBagProblem{publicstaticvoidmain(String[]args){int[]weight={1,3,4};int[]value={15,20,30};intbagSize=4;testWeightBagProblem(weight,value,bagSize);}/***初始化dp......