leetcode111. 二叉树的最小深度
【摘要】 给定一个二叉树,找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树 [3,9,20,null,null,15,7],
3 / \ 9 20 / ...
给定一个二叉树,找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回它的最小深度 2.
思路:见代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int minDepth(TreeNode root) {
if(root == null) return 0;
//左孩子和有孩子都为空的情况,说明到达了叶子节点,返回1
if(root.left == null && root.right == null) return 1;
//左孩子和由孩子其中一个为空,返回较大深度
int m1 = minDepth(root.left);
int m2 = minDepth(root.right);
//其中一个节点为空,说明有一个必为0,所以可以返回m1 + m2 + 1;
if(root.left == null || root.right == null) return m1 + m2 + 1;
//左右孩子都不为空,返回最小深度+1
return Math.min(m1,m2) + 1;
}
}
文章来源: fantianzuo.blog.csdn.net,作者:兔老大RabbitMQ,版权归原作者所有,如需转载,请联系作者。
原文链接:fantianzuo.blog.csdn.net/article/details/103563988
【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)