代码随想录算法训练营第十三天 | leetcode：二叉树的最大深度,最小深度,完全二叉树的节点个数

_zzh 的个人博客 / 47 / 0 / 创建于 2个月前 / 更新于 2个月前

Problem: 104. 二叉树的最大深度

解题方法

使用层序遍历法，在每层遍历的时候增加计数即可。

code

class Solution {

    /**
     * @param TreeNode $root
     * @return Integer
     */
    function maxDepth($root) {
        //深度计数
        $deep =  0;
        if($root == null) return 0;
        $queue = new SplQueue();
        $queue->enqueue($root);
        while(!$queue->isEmpty()){
            $size = $queue->count();
            //每层计数++
            $deep++;
            while($size--){
                $node = $queue->dequeue();
                if($node->left != null) $queue->enqueue($node->left);
                if($node->right != null) $queue->enqueue($node->right);
            }
        }
        return $deep;
    }
}

Problem: 111. 二叉树的最小深度

需要注意的地方

需要使用标志位跳出双重while循环。

解题方法

使用层序遍历法，在每层遍历加入新的左右孩子入队列时，判断第一个左右孩子都为空的情况跳出循环即可。遍历到第一个左右孩子都为空代表，此时节点就是最小深度的叶子节点。

code

class Solution {

    /**
     * @param TreeNode $root
     * @return Integer
     */
    function minDepth($root) {
        $deep =  0;
        if($root == null) return $deep;
        $queue = new SplQueue();
        $queue->enqueue($root);
        //跳出循环标志位
        $end = 0;
        while(!$queue->isEmpty()){
            $size = $queue->count();
            $deep++;
            print_r($deep."\r\n");
            while($size--){
                $node = $queue->dequeue();
                //左右子树都为空的情况直接跳出循环
                if($node->left == null && $node->right == null){
                    //设置循环标志位，跳出内层循环
                    $end = 1;
                    break;
                }
                //一定需要再判断孩子节点是否为空，否则孩子节点为空队列加入了null，第二层就会break退出。
                if($node->left != null) $queue->enqueue($node->left);
                if($node->right != null) $queue->enqueue($node->right);
            }
            //监听内层循环，跳出外层循环
            if($end == 1) break;
        }
        return $deep;
    }
}

Problem: 222. 完全二叉树的节点个数

解题方法

使用层序遍历法，在每层遍历的时候增加节点总计数即可。

code

class Solution {

    /**
     * @param TreeNode $root
     * @return Integer
     */
    function countNodes($root) {
        //总计数
        $count =  0;
        if($root == null) return 0;
        $queue = new SplQueue();
        $queue->enqueue($root);
        while(!$queue->isEmpty()){
            $size = $queue->count();
            //每层都叠加总计数
            $count += $size;
            while($size--){
                $node = $queue->dequeue();
                if($node->left != null) $queue->enqueue($node->left);
                if($node->right != null) $queue->enqueue($node->right);
            }
        }
        return $count;
    }
}