104. 二叉树的最大深度

难度简单1180收藏分享切换为英文接收动态反馈

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：
给定二叉树 [3,9,20,null,null,15,7]，

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

返回它的最大深度 3 。

题解：

简单递归

  • 深度优先遍历，DFS
  • 递归出口：当前节点为空
  • 递归条件：当前节点不为空时，返回其左子树和右子树中深度的最大值加1。
1
2
3
4
5
6
7
8
public int maxDepth(TreeNode root) {
    //终止条件
    if (root == null){
        return 0;
    }
    //树的最大深度等于左子树或者右子树深度的最大值加一，即加上当前根节点
    return 1 + Math.max(maxDepth(root.left),maxDepth(root.right));
}
  • 时间复杂度：O(N)