leetcode-111. 二叉树最小深度 · Tree + 递归

题面

找出二叉树的最小深度(从根节点到某个叶子节点路径上的节点个数最小)。

算法

算法参照二叉树的最大深度,这里需要注意的是当某节点的左右孩子都存在时,就返回左右子树的最小深度如果不都存在,就需要返回左右子树的最大深度(因为子节点不存在的话,通向该子树的路径就走不同,就不存在深度,也无法比较。只能从另一子树方向走。)如果左右孩子不都存在时还取小值,那返回的就是父节点的深度,会出错。

源码 

 1 class Solution {
 2 public:
 3     int minDepth(TreeNode* root) {
 4         if(root == nullptr)
 5             return 0;
 6         if(root->left && root->right)
 7             return min(getDepth(root->left, 1), getDepth(root->right, 1));
 8         else
 9             return max(getDepth(root->left, 1), getDepth(root->right, 1));
10     }
11     
12     int getDepth(TreeNode* p, int deep)
13     {
14         if(p == nullptr)
15             return deep;
16         if(p->left && p->right)
17             return min(getDepth(p->left, deep+1), getDepth(p->right, deep+1));
18         else
19             return max(getDepth(p->left, deep+1), getDepth(p->right, deep+1));
20     }
21 };
全部评论

相关推荐

这算盘打的
程序员小白条:都这样的,都是潜规则,你自己说可以实习一年就行了,实习可以随便跑路的
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-02 17:28
25届每天都在焦虑找工作的事情0offer情绪一直很低落硬撑着面了一个岗位岗位有应酬的成分面试的时候hr给我出各种场景题问的问题比较犀利 有点压力面的感觉感觉有点回答不上来本来就压抑的情绪瞬间爆发了呢一瞬间特别想哭觉得自己特别没用没绷住掉眼泪了事后想想觉得自己挺有病的 真的破大防了
喜欢唱跳rap小刺猬...:我觉得没关系吧,之前有一次面试leader给我压力面,我顶住了压力,结果入职的时候发现组里氛围很差,果断跑路。其实从面试就能大概看出组的情况,面试体验好的组倒是不一定好,但是面试体验不好的组。。。就很难说
面试尴尬现场
点赞 评论 收藏
分享
点赞 评论 收藏
分享
人力小鱼姐:实习经历没有什么含金量,咖啡店员迎宾这种就别写了,其他两段包装一下 想找人力相关的话,总结一下个人优势,结合校园经历里有相关性的部分,加一段自我评价
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务