leetCode ✏Leetcode基础刷题之(111. Minimum Depth of Binary Tree)
✏描述
给定一个二叉树,求二叉树的最小深度.最小深度就是从根节点出发到离他最近的叶子节点的距离(叶子节点没有子节点).
✏题目实例
✏题目分析
思路是深度优先搜索法(DFS).我们还需要考虑两种情况如果是空树,那么深度就是0 .如果根节点左右子树都为空的话,那么深度就是1.递归,如果左节点没有子节点,那么说明右节点有子节点,右节点的深度加1,反之左节点的深度加1.最后的min($left,$right)+1,这里为什么要加1呢,就是为了防止左子树或者右子树为空的情况下,此时比较最小值就是空的一方值为0,这里显然不是0,只有当二叉树为空的时候才是0.
/**
* @param TreeNode $root
* @return Integer
*/
function minDepth($root) {
if(!$root) {
return 0;
}
$left=$this->minDepth($root->left);
$right=$this->minDepth($root->right);
if(!$left) {
return $right+1;
}
if(!$right) {
return $left+1;
}
return $left<$right?$left+1:$right+1;
}
转载链接：https://leetcode.cn/
![[爱了]](/js/img/d1.gif)
![[尴尬]](/js/img/d16.gif)