111.md

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

2019-03-06 吴亲库里 库里的深夜食堂

---

✏️描述

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

---

✏️题目实例

​

✏️题目分析

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

---

联系

​