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

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

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

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

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

一、题目描述

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

二、题目解析

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

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

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

三、动画描述

四、图片描述

五、参考代码

// 登录 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)。

七、相关标签

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

程序员吴师兄算法训练营永久会员

收藏 海报 链接