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

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

解题方法

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

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循环。

解题方法

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

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. 完全二叉树的节点个数

解题方法

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

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;
    }
}
本作品采用《CC 协议》,转载必须注明作者和本文链接
《L01 基础入门》
我们将带你从零开发一个项目并部署到线上,本课程教授 Web 开发中专业、实用的技能,如 Git 工作流、Laravel Mix 前端工作流等。
《L04 微信小程序从零到发布》
从小程序个人账户申请开始,带你一步步进行开发一个微信小程序,直到提交微信控制台上线发布。
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!