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

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;
    }
}