专栏首页苦逼的码农图解精选 TOP 面试题 002 | LeetCode 104. 二叉树的最大深度

图解精选 TOP 面试题 002 | LeetCode 104. 二叉树的最大深度

该系列题目取自 LeetCode 精选 TOP 面试题列表:https://leetcode-cn.com/problemset/top/

题目描述

原题链接:https://leetcode-cn.com/problems/maximum-depth-of-binary-tree

给定一个二叉树,找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明:叶子节点是指没有子节点的节点。

示例:

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

    3
   / \
  9  20
    /  \
   15   7

返回它的最大深度 3 。

解题思路

题目要求求出二叉树的最大深度,我们知道,每个节点的深度与它左右子树的深度有关,且等于其左右子树最大深度值加上 1,可以写作:

maxDepth(root) = max(maxDepth(root.left), maxDepth(root.right)) + 1

[3,9,20,null,null,15,7] 为例,根节点 3 的深度取决于它左右子树的深度:

因其左右子树深度尚不可知,我们需要对其一一求解。

先来看左子树,即以 4 为根节点的子树,因为它没有左右子节点,所以深度为 1:

再来看以 20 为根节点的右子树,同理,它的深度也取决于左右子树的深度:

它的左子节点 15 与右子节点 7 的情况与上述节点 4 相同,左右子节点均为空,所以这两个节点的深度也是 1。由此我们可以得出节点 20 的深度为 2,推导过程如下:

max(左子树最大深度, 右子树最大深度) + 1
=
max(1, 1) + 1
=
1 + 1
=
2

这样一来,我们知道了所有子节点的深度,各节点深度如下:

由此可得根节点 3 的深度为:

max(左子树最大深度, 右子树最大深度) + 1
=
max(1, 2) + 1
=
2 + 1
=
3

上述推导过程整体如下:

maxDepth(3-root)
=
max(maxDepth(4-sub), maxDepth(20-sub)) + 1
=
max(1, max(maxDepth(15-sub), maxDepth(7-sub)) + 1) + 1
=
max(1, maxDepth(1, 1) + 1) + 1
=
max(1, 2) + 1
=
2 + 1
=
3

在推导过程中我们看到 maxDepth() 函数频繁出现,即我们在频繁地求取某节点的最大深度。由此可见,「求节点的最大深度」是该题的子问题,该题最直观的解答方式是用递归求解。

递归设计

在递归算法中,递归函数的设计非常重要,首先我们要先明确该函数的作用,然后再确定何时结束与何时调用该函数

明确函数作用

该函数的作用用一句话概括就是:计算节点的最大深度

  • 函数输入:确定的节点
  • 函数输出:该节点的最大深度

何时结束

当输入的节点为空节点时,我们无需继续计算其子树的深度,此时可以直接结束递归函数,并返回空节点的深度为 0。

何时调用

当输入节点为非空节点时,该节点的深度取决于其左右子树的深度,即:

maxDepth(root) = max(maxDepth(root.left), maxDepth(root.right)) + 1

此时需要进行函数的递归调用。

具体实现

Python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if root is None:
            return 0
        return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

Golang

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    return max(maxDepth(root.Left), maxDepth(root.Right)) + 1
}

func max(a int, b int) int {
    if a > b {
        return a
    }
    return b
}

复杂度

假设节点的数量为 n。

时间复杂度

因为每个节点都需要被访问一次,因此时间复杂度为 O(n)

空间复杂度

考虑到递归使用调用栈(call stack)的情况。

  • 最坏情况:树完全不平衡。例如每个节点都只有右节点,此时将递归 n 次,需要保持调用栈的存储为 O(n)
  • 最好情况:树完全平衡。即树的高度为 log(n),此时空间复杂度为 O(log(n))

总结一下

与树相关的题目常用递归来解,对于递归而言,我们需要明确:

  1. 递归函数的用途
  2. 递归函数的结束条件
  3. 递归函数自身调用的时机

除此之外,在计算空间复杂度时,我们也要考虑到递归时调用栈的情况。

当然了,这道题还可以用迭代法来做,由于篇幅有限,就不在本篇叙述了。大家可以想想要怎么用迭代法解答本题,我们下次再来细说~

本文分享自微信公众号 - 苦逼的码农(di201805)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-12-01

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 为什么C语言不会过时?

    来源:赵岩老师的个人网站:http://zhaoyan.website/blog/index.php/2017/07/15/future/

    帅地
  • 高频手撕算法合集来了!

    基础数据结构的融合是成为庞大系统的基石。比如 Redis 中的跳跃表,数据库索引B+树等,只有对基础的数据结构足够的熟悉才能更容易去理解稍微复杂的结构,就仿佛我...

    帅地
  • 详解一道高频面试题:接雨水

    接雨水这道题目挺有意思,在面试题中出现频率还挺高的,本文就来步步优化,讲解一下这道题。

    帅地
  • 图解精选 TOP 面试题 002 | LeetCode 104. 二叉树的最大深度

    题目要求求出二叉树的最大深度,我们知道,每个节点的深度与它左右子树的深度有关,且等于其左右子树最大深度值加上 1,可以写作:

    江不知
  • 图像处理开发者必读

    小编作为一个图像与计算机视觉的开发者,总结了一下作为图像处理开发工程师应该知道或者掌握的图像处理知识点。跟大家分享一下,以备大家学习方便。 图像像素操作 -...

    OpenCV学堂
  • git基础知识

    git config --global user.email'lirulei90@126.com'

    二狗不要跑
  • 第一次发布自己的npm包

    在做表单的时候,会遇到很多的表单项的验证工作,几乎很多验证都是重复的,有一个比较好的lodash库来做了这些工作,但是里面有些方法和实际的业务工作有些不符。比如...

    贺贺V5
  • How do I know that Association is internally implemented by inner join or outer association

    How do I know that Association is internally implemented by inner join or outer ...

    Jerry Wang
  • 开发者必备Mysql数据库的常用命令

    关于mysql数据库的一些常用命令操作,经常不用就很容易忘记,今天再次复习做了一些笔记加深印象,如何用命令连接mysqla数据库进行增删改查,以下是操作过程。

    汤清丽
  • 基于Win10极简SonarQube C#代码质量分析

    博客有些好些时间未更新了,这几个月的时间里,离开了实习的公司、大学毕了业、来了新公司、转了户口,有点忙,最近总算稍微闲下来了,打算重新拾起博客,坚持写下去。

    码农阿宇

扫码关注云+社区

领取腾讯云代金券