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

2019-3-5 星期二   开始吧

题目描述

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

题目分析

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

 运行结果