专栏首页IT那个小笔记104 二叉树最大深度

104 二叉树最大深度

01

题目信息

题目地址: https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/

给定一个二叉树,找出其最大深度。二叉树的深度根节点到最远叶子节点的最长路径上的节点数。

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

示例:

给定二叉树 [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
返回它的最大深度 3 。

02

概述

树的开篇第一题其实也是比较简单的,但它的目的是让我们初步认识树这样一个结构。二叉树每个节点有两个子节点也就是两个指针。大概结构如下:

public class TreeNode {
    //节点内容值
    int val;
    //两个指针
    TreeNode left;
    TreeNode right;
    //构造方法
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

03

解法一:深度优先搜索(DFS)

递归的想法,最大深度 = 1 + Max( L0(left) , L0(right))。而每个子树再找到它最大的深度。下图就是这样一个过程,图中省略一些东西只画了一部分理解这样一个思路就ok

public int maxDepth(TreeNode root) {
    if(root == null) return 0; // 递归出口  
    return Math.max(this.maxDepth(root.left), this.maxDepth(root.right)) + 1;
}

04

解法二:广度优先搜索(BFS)

上面是递归,这里是迭代的方式,输入root节点判断是否存在存在则深度+1,再判断下一层节点(输入1层两个节点)对一个节点判断有无子节点,无则出,有则把它的子节点先加进来再出,注意这里是一个先进先出的关系(排队)因为是一层一层的遍历完

public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    int result = 0;
    while (!queue.isEmpty()) {
    //每层每个节点的遍历
        for(int i = quene.size(); i > 0; i--){
            TreeNode node = queue.poll();
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        result++;
    }
    return result;
}

05

总结

合集中树的第一题,总体来说熟悉树的基本结构体会遍历的操作

本文分享自微信公众号 - IT那个小笔记(Jasper-zh_blog),作者:木瓜煲鸡脚

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

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 104. 二叉树的最大深度

    Michel_Rolle
  • 【Leetcode】104. 二叉树的最大深度

    求最大深度,和深度相关,我们很容易想到用层序遍历。每遍历一层,就深度加1, 怎么记录是第几层我们之前的文章中讲过了。

    Leetcode名企之路
  • Leetcode 104. 二叉树的最大深度

    二叉树根节点为空,则树高度为 0,根节点不为空,则高度为左子树、右子树的最大值加一。

    zhipingChen
  • leetcode:104二叉树的最大深度

    思路:用深度优先遍历。 深度优先遍历是尽可能深的遍历这棵树。 怎么做? 新建一个变量记录每一个节点的层级,找到最大的层级即可。

    贵哥的编程之路
  • LeetCode 104. 二叉树的最大深度

    freesan44
  • LeetCode | 104.二叉树的最大深度

    这次来写一下 LeetCode 的第 104 题,二叉树的最大深度。

    码农UP2U
  • LeetCode 104. 二叉树的最大深度

    https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/

    freesan44
  • Leetcode No.104 二叉树的最大深度

    如果我们知道了左子树和右子树的最大深度 l 和 r,那么该二叉树的最大深度即为 max(l,r)+1

    week
  • 【leetcode系列】104. 二叉树的最大深度

    https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/description/

    lucifer210
  • 力扣 (LeetCode)-104. 二叉树的最大深度,图

    每天学习编程,让你离梦想更新一步,感谢不负每一份热爱编程的程序员,不论知识点多么奇葩,和我一起,让那一颗四处流荡的心定下来,一直走下去,加油,2021加油!欢迎...

    达达前端
  • 画解算法:104. 二叉树的最大深度

    https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/

    灵魂画师牧码
  • ​LeetCode刷题实战104:二叉树的最大深度

    https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/

    程序IT圈
  • LeetCode刷题记录:104. 二叉树的最大深度

    英雄爱吃土豆片
  • 每天一道leetcode-104.二叉树的最大深度

    今天的题目 每天的题目见github(看最新的日期): https://github.com/gzc426

    乔戈里
  • Leetcode|二叉树的属性|104. 二叉树的最大深度

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

    Given a binary tree, find its maximum depth.

    爱写bug
  • 【LeetCode 104.二叉树的最大深度】双解法:递归+非递归

    递归的写法非常直观。对于一棵二叉树来说,它的高度等于左右子树的高度最大值,加上 1。

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

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

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

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

    江不知

扫码关注云+社区

领取腾讯云代金券