[每日一题] 第三题:二叉树的深度

题目描述

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

例如:

给定二叉树 [3,9,20,null,null,15,7]

   3
   / \
  9  20
    /  \
   15   7

返回它的最大深度 3 。

提示:

节点总数 <= 10000

题解

后续遍历(DFS)

算法思想

树的后续遍历/深度遍历往往利用 或者 递归 实现,本文使用递归实现

关键点:此数的深度和其左(右)子树的深度之间的关系。显然,此树的深度 等于 左子树的深度右子树的深度 中的 最大值 +1 。

算法解析

  1. 终止条件:当 root 为空,说明已越过叶节点,因此要返回深度 0。

  2. 递归工作:本质上是要对树做后续遍历。

    1. 计算节点 root 的左子树的深度,即调用 maxDepth(root.left)

    2. 计算节点 root 的右子树的深度,即调用 maxDepth(root.left)

  3. 返回值: 返回 此树的深度 ,即 max(maxDepth(root.left), maxDepth(root.right)) + 1

复杂度

时间复杂度 O(N) : N 为树的节点数量,计算树的深度需要遍历所有节点。

空间复杂度 O(N) : 最差情况下(当树退化为链表时),递归深度可达到 N 。

代码

class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}

个人理解

直接记住即可。

层序遍历(BFS)

树的层序遍历 / 广度优先搜索往往利用 队列 实现。

关键点: 每遍历一层,则计数器 +1 ,直到遍历完成,则可得到树的深度。

算法解析

特例处理: 当 root 为空,直接返回 深度 0。

初始化: 队列 queue (加入根节点 root),计数器 res = 0

循环遍历: 当 queue 为空时跳出。

初始化一个空列表 tmp ,用于临时存储下一层节点;

遍历队列: 遍历 queue 中的各节点 node,并将其左子节点和右子节点加入 tmp

更新队列: 执行 queue = tmp ,将下一层节点赋值给 queue

统计层数: 执行 res += 1 ,代表层数加 1;

返回值: 返回 res 即可。

代码

class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        List<TreeNode> queue = new LinkedList<>() {{ add(root); }}, tmp;
        int res = 0;
        while(!queue.isEmpty()) {
            tmp = new LinkedList<>();
            for(TreeNode node : queue) {
                if(node.left != null) tmp.add(node.left);
                if(node.right != null) tmp.add(node.right);
            }
            queue = tmp;
            res++;
        }
        return res;
    }
}

个人理解

记住即可。

题目出处

作者:jyd
链接:leetcode-cn.com/problems/er-cha-sh...
来源:力扣(LeetCode)

本作品采用《CC 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

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