类似树的深度问题，都可以使用递归实现：

确定递归的参数和返回值：参数就是传入树的根节点，返回值就是树的深度；

确定终止条件：如果为空节点的话，就返回0，表示高度为0；

确定单层递归的逻辑：如果是二叉树，那么先求它的左子树的深度，再求的右子树的深度，最后取左右深度最大的数值，最后再+1（加1是因为算上当前中间节点）就是目前节点为根节点的树的深度。

具体到N叉树，代码如下所示：

时间复杂度：O(n)O(n)O(n)，其中nnn为NNN叉树节点的个数。每个节点在递归中只被遍历一次。

空间复杂度：O(height)O(\textit{height})O(height)，其中height\textit{height}height表示NNN叉树的高度。递归函数需要栈空间，而栈空间取决于递归的深度，因此空间复杂度等价于NNN叉树的高度。

二叉树的遍历，其实也是DFS的一种方式，我们可以参考二叉树的遍历，使用迭代的方式进行遍历，最后更新NNN叉树的最大深度。

时间复杂度：O(n)O(n)O(n)，其中nnn为NNN叉树节点的个数。

方法三：BFS

使用BFS进行求解，实质是对多叉树进行分层处理，BFS队列里存放的是当前层的所有节点。

值得注意的是，因为队列Queue会不断增加，所以必须从size往下添加。

每次拓展下一层的时候，需要将队列里的所有节点都拿出来进行拓展，当过程结束，意味着达到最大层数，所记录的最大层数即是答案。

时间复杂度：O(n)O(n)O(n)，其中nnn为NNN叉树的节点个数。与方法一同样的分析，每个节点只会被访问一次。

空间复杂度：O(n)O(n)O(n)，此方法空间的消耗取决于队列存储的元素数量，其在最坏情况下会达到O(n)O(n)O(n)。

版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！