[AcWing]71. 二叉树的深度
[AcWing]71. 二叉树的深度
输入一棵二叉树的根结点,求该树的深度。
从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。
数据范围
树中节点数量 [0,500]
。
样例
1 |
|
算法思想
对二叉树进行DFS遍历,在这个过程中,进入下一子树,则depth + 1
。
取左右子树depth
的最大值。
代码实现
1 |
|
时间复杂度
DFS遍历,每个节点只被遍历一次,时间复杂度是O(n)
。
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Phbeats-Blog!
评论