题目#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))

代码分析

想拿到最大深度，可分为两种情况

• 根节点为空，则最大深度为0if (root == null) return 0
• 根节点不为空，则最大深度为左右子树的最大深度取最大值加一return 1 + max(maxDepth2(root.left), maxDepth2(root.right))