专栏首页爱写BugLeetCode 104: 二叉树的最大深度 Maximum Depth of Binary Tree

LeetCode 104: 二叉树的最大深度 Maximum Depth of Binary Tree

题目:

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

Given a binary tree, find its maximum depth.

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

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

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

Note: A leaf is a node with no children.

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

    3
   / \
  9  20
    /  \
   15   7

返回它的最大深度 3 。

解题思路:

总体而言, 有两种思路:

  • BFS 广度优先遍历时用一个变量记录深度
  • DFS 深度优先遍历时保留每次遍历到叶子结点时的最大深度

对于这道题, 用 DFS 深度优先遍历时若使用递归方法, 又可分为两种思路: 自顶向下, 自底向上

具体可以看这篇文章:

树的遍历 Traverse a Tree

类似题目有:

LeetCode 559: N 叉树的最大深度 Maximum Depth of N-ary Tree

"自顶向下"递归解法:

Java:

class Solution {
    public int maxDepth(TreeNode root) {
        // 基线条件
        if (root == null)
            return 0;
        // 递归左子结点
        int leftDepth = maxDepth(root.left);
        // 递归右子结点
        int rightDepth = maxDepth(root.right);
        // 返回当前结点的子树最大深度
        return Math.max(leftDepth, rightDepth) + 1;
    }
}

Python:

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        # 基线条件
        if not root:
            return 0
        # 递归左子结点
        left_depth = self.maxDepth(root.left)
        # 递归右子结点
        right_depth = self.maxDepth(root.right)
        # 返回当前结点的子树最大深度
        return max(left_depth, right_depth)+1

"自底向上"递归解法

Java:

class Solution {
    // 记录最大深度
    int res = 0;

    public int maxDepth(TreeNode root) {
        maxDepthHelper(root, 1);
        return res;
    }

    private void maxDepthHelper(TreeNode node, int depth) {
        // 基线条件
        if (node == null)
            return;
        // 当前结点为叶子结点时, 刷新最大深度
        if (node.left == null && node.right == null)
            res = Math.max(res, depth);
        // 递归左右子结点
        maxDepthHelper(node.left, depth + 1);
        maxDepthHelper(node.right, depth + 1);
    }
}

Python:

class Solution:

    def maxDepth(self, root: TreeNode) -> int:
        self.max_depth = 0 # 记录最大深度
        maxDepthHelper(root, 1)
        return max_depth

    def maxDepthHelper(self, node: TreeNode, depth: int):
        #  基线条件
        if not node:
            return
        # 当前结点为叶子结点时, 刷新最大深度
        if not (node.left or node.right):
            self.max_depth = max(self.max_depth, depth)
        # 递归左右子结点
        maxDepthHelper(node.left, depth+1)
        maxDepthHelper(node.right, depth+1)

本文分享自微信公众号 - 爱写Bug(iCodeBugs),作者:爱写Bug

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

原始发表时间:2020-01-20

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Leetcode747至少是其他数字两倍的最大数

    在一个给定的数组nums中,总是存在一个最大元素 。查找数组中的最大元素是否至少是数组中每个其他数字的两倍。如果是,则返回最大元素的索引,否则返回-1。

    爱写bug
  • LeetCode 747:至少是其他数字两倍的最大数Largest Number At Least Twice of Other

    在一个给定的数组nums中,总是存在一个最大元素 。查找数组中的最大元素是否至少是数组中每个其他数字的两倍。如果是,则返回最大元素的索引,否则返回-1。

    爱写bug
  • Leetcode724:寻找数组的中心索引(java、python3)

    给定一个整数类型的数组 `nums`,请编写一个能够返回数组**“中心索引”**的方法。

    爱写bug
  • Java 二维数组按指定列排序(一)

    private static void printArr(int[][] nums) {

    用户7886150
  • codeforces 429A(dfs)

    给定一棵树,树的每个结点上有一个值,你可以对树上的值进行异或操作,求使树上的结点值成为目标值所需的最少操作

    dejavu1zz
  • UNPv13:#第4章#基于TCP套接字编程

    概述 ? socket函数 #inlcude <sys/socket.h> int socket(int family, int type, int prot...

    _gongluck
  • LeetCode 1319. 连通网络的操作次数(BFS/DFS/并查集)

    用以太网线缆将 n 台计算机连接成一个网络,计算机的编号从 0 到 n-1。 线缆用 connections 表示,其中 connections[i] = [...

    Michael阿明
  • Android实现多维商品属性SKU选择

    最近又做到这一块的需求,以前也做过类似仿淘宝的属性选择,当时在网上下载的demo参考,最多也支持两组商品属性,用的两个gridview结合,扩展性很差,这次不打...

    砸漏
  • 种树 差分约束|贪心

    每次种的树在重叠区间越多,种的树越少。只有结束位置才会重合,就对区间结束的位置从小到大排序。

    用户2965768
  • pta 天梯地图 (Dijkstra)

    本题要求你实现一个天梯赛专属在线地图,队员输入自己学校所在地和赛场地点后,该地图应该推荐两条路线:一条是最快到达路线;一条是最短距离的路线。题目保证对任意的查...

    ShenduCC

扫码关注云+社区

领取腾讯云代金券