请勿第一时间看答案，先自己思考，思考不出来，再看答案
思考题：二叉树的最大深度
题目描述
给定一个二叉树 root ，返回其最大深度。
二叉树的最大深度：是指从根节点到最远叶子节点的最长路径上的节点数。如下图所示的二叉树，最大深度为 3
原题地址：leetcode 104
解题思路
使用递归来解题，主要只关注两个问题
- 找到规律：如何拆分相同子问题
- 找到终止条件
我们假定函数 maxDepth(root)
已经可以计算出以 root
为根节点的二叉树的最大深度，那么，对于左右两个子节点，我们会返回值更大的那一边，所以就有如下关系
Math.
max
(
maxDepth
(root.left),
maxDepth
(root.right))
当然，每计算一次，会增加一层，所以最终的结果应该是
Math.
max
(
maxDepth
(root.left),
maxDepth
(root.right))
+
1
最后我们来思考终止条件。理论上来说，当我们找到叶子节点时，最大深度为 1，所以我们可以返回 1，但是由于在上面的规律中，我们会将左节点与右节点继续传入，叶子节点的左节点与右节点为空
所以，终止条件为
if
(
!
root)
return
0
完整代码如下
answers.ts
10
class
TreeNode
{
20
val
:
number
30
left
:
TreeNode
|
null
40
right
:
TreeNode
|
null
50
constructor
(
val
?:
number
,
left
?:
TreeNode
|
null
,
right
?:
TreeNode
|
null
) {
60
this
.val
=
(val
===
undefined
?
0
:
val)
70
this
.left
=
(left
===
undefined
?
null
:
left)
80
this
.right
=
(right
===
undefined
?
null
:
right)
90
}
10
}
11
12
export function
maxDepth
(
root
:
TreeNode
|
null
)
:
number
{
13
if
(root
===
null
) {
14
return
0
15
}
16
return
Math.
max
(
maxDepth
(root.left),
maxDepth
(root.right))
+
1
17
};
上一篇
最大连续 1 的个数
下一篇
平衡二叉树判断
专栏首页
到顶
专栏目录