小学生都能看懂的题解 | #二叉树的最大深度#

故事背景

想象你在一个大树下玩耍，这棵树有很多分支。你的任务是找出从树的根部（最底部）到任何一个叶子（没有分叉的地方）的最长路径有多长。这条最长路径上的节点数就是树的最大深度。

游戏规则

游戏的规则很简单：

1. 从根部开始。
2. 每往下走一步就加一。
3. 记住走到叶子时的步数。
4. 找出所有叶子中最大的步数。

示例

让我们通过一个简单的例子来理解这个过程：

示例 1

假设树是这样的：

    1
   /
  2

从根部（1）到叶子（2）需要走一步。

最终的结果应该是：2

示例 2

假设树是这样的：

    1
   / \
  2   3
 /     \
4       5

从根部（1）到叶子（4）需要走三步，从根部（1）到叶子（5）也需要走三步。

最终的结果应该是：3

示例代码

现在我们用Java来实现这个过程，我们会使用递归的方式，因为递归更容易理解和实现。

java深色版本// 定义二叉树节点
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class BinaryTreeMaxDepth {

    /**
     * 计算二叉树的最大深度
     * @param root 二叉树的根节点
     * @return 树的最大深度
     */
    public int maxDepth(TreeNode root) {
        // 如果树为空，深度为0
        if (root == null) {
            return 0;
        }

        // 计算左子树的最大深度
        int leftDepth = maxDepth(root.left);

        // 计算右子树的最大深度
        int rightDepth = maxDepth(root.right);

        // 取左右子树最大深度中的较大者，并加1（当前节点）
        return Math.max(leftDepth, rightDepth) + 1;
    }

    
}

解释

1. 定义二叉树节点：
1. 使用 TreeNode 类来表示二叉树的节点，每个节点包含一个值 val 和两个指向左右孩子的指针 left 和 right。
2. 计算最大深度的方法：
1. maxDepth 方法接收一个 TreeNode 类型的参数 root，表示二叉树的根节点。
2. 如果当前节点为空，则返回 0，因为没有节点就没有深度。
3. 递归地计算左子树的最大深度。递归地计算右子树的最大深度。
4. 返回两者中的较大值加上当前层（+1）作为最大深度。

如果这篇文章对你有帮助，请点个免费的赞👍，让它能帮助更多的人。