题目#104.二叉树的最大深度
给定一个二叉树,找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树 [3,9,20,null,null,15,7],
返回它的最大深度 3 。
题目分析
每个节点都对应着一个深度信息,但是在节点上却并没有体现出来,如果节点上能绑定一个带有深度的值那这个题不就很方便解决了吗?按照这个思路,我们可以设置一个全局变量,在二叉树进行遍历的时候,能够时时更新深度,于是代码如下。
代码
private var depth = 0
fun maxDepth(root: TreeNode?): Int {
dfs(root, 0)
return depth
}
private fun dfs(root: TreeNode?, level: Int) {
if (root == null) {
depth = max(depth, level)
return
}
dfs(root.left, level + 1)
dfs(root.right, level + 1)
}
代码分析
在二叉树中,深度优先搜索的代表典型就是二叉树的前中后序遍历,上面的代码仅仅展示了二叉树的前序遍历,二叉树遍历完成之后,depth已经保存了整个二叉树的最大深度depth = max(depth, level)
,当然,这种实现方式仅是其中一种以深度优先搜索实现的代码,这题使用广度优先搜索会更简单且思路更清晰。
广度优先搜索
广度优先搜索(Breadth First Search),又称为"宽度优先搜索"或"横向优先搜索",简称BFS。
思路分析
想要拿到二叉树的最大深度,则只需要拿到左右子节点的最大深度然后取最大值并加一就可以,代码如下:
fun maxDepth(root: TreeNode?): Int {
if (root == null) return 0
return 1 + max(maxDepth2(root.left), maxDepth2(root.right))
}
使用kotlin语法糖,代码可进一步简化成:
fun maxDepth(root: TreeNode?): Int = if (root == null) 0 else 1 + max(maxDepth(root.left), maxDepth(root.right))
代码分析
想拿到最大深度,可分为两种情况
- 根节点为空,则最大深度为0
if (root == null) return 0
- 根节点不为空,则最大深度为左右子树的最大深度取最大值加一
return 1 + max(maxDepth2(root.left), maxDepth2(root.right))