二叉树的深度咋算(二叉树的最大深度)

二叉树的深度咋算(二叉树的最大深度)(1)

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

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

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

示例:

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

二叉树的深度咋算(二叉树的最大深度)(2)

返回它的最大深度 3 。

二叉树的深度咋算(二叉树的最大深度)(3)

我们能想到的最简单的方式估计就是递归了,也就是下面这个图

二叉树的深度咋算(二叉树的最大深度)(4)

如果对递归不熟悉的话可以看下我前面讲的关于复仇一个故事362,汉诺塔。下面我们来画个图来分析下

二叉树的深度咋算(二叉树的最大深度)(5)

看明白了上面的过程,代码就容易多了,我们看下

二叉树的深度咋算(二叉树的最大深度)(6)

除了递归,我们还可能想到的就是BFS(宽度优先搜索算法(又称广度优先搜索)),他的实现原理就是一层层遍历,统计一下总共有多少层,我们来画个图分析一下。

二叉树的深度咋算(二叉树的最大深度)(7)

一层一层往下走,统计总共有多少层,我们来看下代码

二叉树的深度咋算(二叉树的最大深度)(8)

想到BFS我们一般会和DFS联想到一起,DFS是深度优先搜索算法,我们先来看下代码

二叉树的深度咋算(二叉树的最大深度)(9)

这里使用了两个栈,一个是存储节点的,一个是存储每个节点到根节点总共经过多少个节点(包含根节点和当前节点)。

如果喜欢这篇文章还可以关注微信公众号“数据结构和算法”,查看更多的算法题

,

免责声明:本文仅代表文章作者的个人观点,与本站无关。其原创性、真实性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容文字的真实性、完整性和原创性本站不作任何保证或承诺,请读者仅作参考,并自行核实相关内容。文章投诉邮箱:anhduc.ph@yahoo.com

    分享
    投诉
    首页