图解 | LeetCode #104 二叉树的最大深度

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

示例:

思路分析
层序遍历
第一种思路是对二叉树进行层序遍历，每遍历一层，二叉树的深度加一，直到所有节点考察完毕。这样，就可以计算出二叉树的最大深度了。
这里的关键是要知道每层需要遍历多少个节点。主要方法是：

• 将当前考察的节点放入队列，然后开始遍历队列中的元素；

• 在取出队列中元素之前，先计算队列中元素个数，即当前这一层共有几个节点；

• 然后，通过内层for循环将队列中的元素全部取出，每取出一个元素时，若其左子树或右子树不为空，则将其加入队列，等待下一次遍历。

代码实现如下：

首先，将根节点3放入队列。然后，开始遍历队列，这时队列不为空，最大深度maxDepth加一，即当前最大深度为1。

接着，3出队，它的左右子树都不为空，因此加入队列。这时，队列不为空， 最大深度maxDepth加一，即当前最大深度为2 。

接着，队列中的9和20出队，9的左右子树都为空，20的左右子树不为空，因此将其左右子树加入队列。这时，队列不为空， 最大深度maxDepth加一，即当前最大深度为3 。

递归思想
第二种思路是由于二叉树有其天然的递归属性，即其左右子树都是同样的二叉树结构，因此可以借助递归思想来求解该题目。
主要思路是：对于当前节点来说，它只需要知道其左子树和右子树的深度，然后取两者中的最大值加上一，就计算出了以其为根节点的二叉树的深度。
题目给出的示例如下：
对于根节点3来说，其左子树是节点9，右子树是以20为根节点二叉树。
对于以20为根节点的二叉树来说，其左子树是节点15，右子树是节点7。因此，其左右子树的深度都为1，故以20为根节点的二叉树其深度是2。
知道了以20为根节点的二叉树深度是2，则对于以3位根节点的二叉树来说其深度为右子树的深度2加1，即3。