Leetcode基础刷题之(111. Minimum Depth of Binary Tree)

Leetcode · curry · 于 24天前 发布 · 24 次阅读

题目描述

给定一个二叉树,求二叉树的最小深度.最小深度就是从根节点出发到离他最近的叶子节点的距离(叶子节点没有子节点).

题目分析

思路是深度优先搜索法(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;
}

本文由 curry 创作,采用 知识共享署名 3.0 中国大陆许可协议 进行许可。 可自由转载、引用,但需署名作者且注明文章出处。

共收到 0 条回复 二叉树 php 算法
没有找到数据。
添加回复 (需要登录)
需要 登录 后方可回复, 如果你还没有账号请点击这里 注册
吴亲库里的深夜食堂