104 二叉树的最大深度

一、题目

给定一个二叉树 root ，返回其最大深度。

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

二、题解

思路： 用递归（深度优先）求解。一棵树的最大深度，等于其左右子树最大深度的较大值再加 1（加上当前根节点这一层）。

  • 递归终止条件：节点为空时深度为 0。
  • 分别递归求出左子树深度 countL 和右子树深度 countR，返回 Math.max(countL, countR) + 1。
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

class Solution {
    public int maxDepth(TreeNode root) {
        // 定义两个变量，分别用来接收左子树和右子树的深度
        int countL = 0, countR = 0;

        // 【递归的终止条件 / 边界情况】
        // 如果当前节点是空的（说明已经越过了叶子节点，到达了最底部）
        // 空节点的深度自然是 0，直接返回。
        if(root == null) {
            return 0;
        } else {
            // 【步骤 1：探测左子树的深度】
            // 派一个小机器人去左边探路，一直探到底，
            // 机器人回来时，会汇报左子树的最大深度，存入 countL。
            countL = maxDepth(root.left);

            // 【步骤 2：探测右子树的深度】
            // 同样地，派一个小机器人去右边探路，
            // 机器人回来时，会汇报右子树的最大深度，存入 countR。
            countR = maxDepth(root.right);

            // 【步骤 3：计算并返回当前节点的总深度】
            // 左右两边的深度都知道了，整棵树到底有多深呢？
            // 取左右两边的最大值 (Math.max)，然后再加 1（加上当前节点自己这一层），
            // 将这个最终结果返回给上一层。
            return Math.max(countL, countR) + 1;
        }
    }
}

时间复杂度：O(n)O(n)

空间复杂度：O(h)O(h)

评论