[Leetcode][559. N叉树的最大深度] 3种方法:递归,DFS和BFS
By Long Luo
方法一:递归
思路与算法:
类似树的深度问题,都可以使用递归实现:
- 确定递归的参数和返回值:参数就是传入树的根节点,返回值就是树的深度;
- 确定终止条件:如果为空节点的话,就返回0,表示高度为0;
- 确定单层递归的逻辑:如果是二叉树,那么先求它的左子树的深度,再求的右子树的深度,最后取左右深度最大的数值,最后再+1(加1是因为算上当前中间节点)就是目前节点为根节点的树的深度。
具体到N叉树,代码如下所示:
1 | // Recursion time: O(n) space: O(n) |
复杂度分析
-
时间复杂度:,其中为叉树节点的个数。每个节点在递归中只被遍历一次。
-
空间复杂度:,其中表示叉树的高度。递归函数需要栈空间,而栈空间取决于递归的深度,因此空间复杂度等价于叉树的高度。
方法二:DFS迭代
二叉树的遍历,其实也是DFS
的一种方式,我们可以参考二叉树的遍历,使用迭代的方式进行遍历,最后更新叉树的最大深度。
1 | // DFS time: O(n) space: O(n) |
复杂度分析
-
时间复杂度:,其中为叉树节点的个数。
-
空间复杂度:,每个节点都需要入栈出栈一次。
方法三:BFS
思路与算法:
使用BFS
进行求解,实质是对多叉树进行分层处理,BFS
队列里存放的是当前层的所有节点。
值得注意的是,因为队列Queue会不断增加,所以必须从size
往下添加。
每次拓展下一层的时候,需要将队列里的所有节点都拿出来进行拓展,当过程结束,意味着达到最大层数,所记录的最大层数即是答案。
1 | // BFS time: O(n) space: O(n) |
复杂度分析:
-
时间复杂度:,其中为叉树的节点个数。与方法一同样的分析,每个节点只会被访问一次。
-
空间复杂度:,此方法空间的消耗取决于队列存储的元素数量,其在最坏情况下会达到。
All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)
Explore More Leetcode Solutions. 😉😃💗