[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.

题目大意:

给一个二叉树,寻找它的最大深度。

这个最大深度就是从根节点到叶子节点的最长路线所经过的节点。


 

这题难度是Easy。可是我对二叉树的概念只剩下前、中、后序遍历与基本搜索的递归算法。什么?深度?这可就真是强人所难了。

我确实不知道这题如何下手。于是我搜狗了一下。得到的答案异常简单。

就,递归一下就好了。

“(引用)

原文地址:http://www.kancloud.cn/kancloud/data-structure-and-algorithm-notes/73030

其中那个递归的算法。代码如下:

其中,该代码中使用的是后序遍历,即先访问左子树,再访问右子树,最后访问根节点。我试着走了一遍,发现这个递归会先一步一步挖到这个树的左边那个最深的树,然后再走右边,和右边不断比较,取最大值,并进行 +1 来作为它自己的返回值(也就是说他把自己也作为距离 1 加进去了)。这样后序遍历的结果就是所有的叶子都被访问到。

可是众所周知,二叉树这玩意肯定不止递归这一种解法。而前辈也提出了一种用栈的方法去防止递归造成的栈溢出。然后他(她)说是用前面后序遍历去修改的。

“(引用)

原文地址:http://www.kancloud.cn/kancloud/data-structure-and-algorithm-notes/73030

使用递归可能会导致栈空间溢出,这里使用显式栈空间(使用堆内存)来代替之前的隐式栈空间。从上节递归版的代码(先处理左子树,后处理右子树,最后返回其中的较大值)来看,是可以使用类似后序遍历的迭代思想去实现的。

首先使用后序遍历的模板,在每次迭代循环结束处比较栈当前的大小和当前最大值max_depth进行比较。

/*以下代码的注释是我自己补的*/

然后该前辈还说,可以用队列。(简直就是计算机概论课的复习啊)

“(引用)

原文地址:http://www.kancloud.cn/kancloud/data-structure-and-algorithm-notes/73030

题解3 – 迭代(队列)

在使用了递归/后序遍历求解树最大深度之后,我们还可以直接从问题出发进行分析,树的最大深度即为广度优先搜索中的层数,故可以直接使用广度优先搜索(BFS)求出最大深度。