大家好,我是程序员吴师兄,欢迎来到 图解剑指 Offer 结构化专栏,在这个专栏里我将和大家一起学习如何用结构化的思维来思考、解题、写代码,希望能帮助你即使在面试的时候紧张也能做对。

AlgoMooc 算法慕课网,每道题目都有动画和图片,致力于帮助每个程序员通过算法面试!

今天分享的题目来源于 LeetCode 上的剑指 Offer 系列面试题剑指 Offer 55 – I. 二叉树的深度

题目汇总链接:https://www.algomooc.com/jianzhioffer

一、题目描述

输入一棵二叉树的根节点,求该树的深度。从根节点到叶节点依次经过的节点(含根、叶节点)形成树的一条路径,最长路径的长度为树的深度。

二、题目解析

题目要求我们统计二叉树的深度,另外一个表达意思就是二叉树有多少层

所有可以直接使用二叉树的层序遍历操作,每遍历一层,计数器加一,这样,层序遍历完成后,结果就有了。

在层序遍历的过程中,我们可以设置两个数组,一个数组 queue 用来存储当前层的节点,一个数组 temp 用来存储当前节点的子节点,当当前层的节点已经统计完毕,需要开始统计下一层的节点数据时,只需要将 temp 覆盖掉 queue 即可。

三、动画描述

隐藏内容
  • 普通用户购买价格:5积分
  • 会员用户购买价格:免费
  • 永久会员用户购买价格:免费推荐

四、图片描述

剑指 Offer 55 - I. 二叉树的深度.002

剑指 Offer 55 - I. 二叉树的深度.003

剑指 Offer 55 - I. 二叉树的深度.004

剑指 Offer 55 - I. 二叉树的深度.005

剑指 Offer 55 - I. 二叉树的深度.006

剑指 Offer 55 - I. 二叉树的深度.007

剑指 Offer 55 - I. 二叉树的深度.008

剑指 Offer 55 - I. 二叉树的深度.009

剑指 Offer 55 - I. 二叉树的深度.010

剑指 Offer 55 - I. 二叉树的深度.011

剑指 Offer 55 - I. 二叉树的深度.012

剑指 Offer 55 - I. 二叉树的深度.013

剑指 Offer 55 - I. 二叉树的深度.014

五、参考代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
class Solution {
    public int maxDepth(TreeNode root) {
        // 边界情况判断
        if(root == null) return 0;

        // 用来存储二叉树中的节点
        List<TreeNode> queue = new LinkedList<>();

        // 用来存储 queue 中节点的子节点
        List<TreeNode> temp = new LinkedList<>();

        // 将二叉树的根节点加入到 queue
        queue.add(root);

        // 初始化二叉树的深度为 0
        int res = 0;

        // 循环遍历 queue,直到为空,说明已经遍历了二叉树所有的节点
        while(!queue.isEmpty()) {

            // 对于 queue 中的每一个节点都设置一个数组 temp 用来存储当前节点的子节点数据
            temp = new LinkedList<>();

            // 把当前节点的所有子节点添加到 temp 中
            for(TreeNode node : queue) {
                // 添加当前节点的左子节点到 temp 中
                if(node.left != null) temp.add(node.left);
                // 添加当前节点的右子节点到 temp 中
                if(node.right != null) temp.add(node.right);
            }

            // 二叉树的当前这一层已经统计结束,开始统计下一层的节点情况
            queue = temp;

            // 二叉树的当前这一层已经统计结束,层数加一
            res++;
        }

        // 返回统计结果
        return res;
    }
}

六、复杂度分析

时间复杂度

时间复杂度为 O(N)。

空间复杂度

空间复杂度为 O(N)。

七、相关标签

  • 二叉树
  • 深度优先搜索
  • 广度优先搜索

发表评论

邮箱地址不会被公开。 必填项已用*标注

评论(1)