当前位置：首页 > article >正文

算法：计算二叉树的最大深度（Java实现）

article 2024/11/10 11:34:01

思路

定义问题：最大深度（或称为最大层数）是从根节点到最远叶子节点的路径上的节点数。我们需要找到这个最长路径的节点数。
递归的基本思路：
- 对于每个节点，我们需要计算其左子树的最大深度和右子树的最大深度。
- 节点的最大深度是其左子树和右子树最大深度中的较大值加一（加上当前节点）。
递归终止条件：
- 如果节点为空（即树为空或到达叶子节点的子节点），深度为0。
递归步骤：
- 计算当前节点的左子树深度。
- 计算当前节点的右子树深度。
- 当前节点的深度是左子树和右子树深度的最大值加一。

示例代码解析

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class BinaryTree {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftDepth = maxDepth(root.left);  // 递归计算左子树的深度
        int rightDepth = maxDepth(root.right); // 递归计算右子树的深度
        return Math.max(leftDepth, rightDepth) + 1; // 当前节点的深度是左右子树深度的最大值加1
    }

    public static void main(String[] args) {
        // 示例用法
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        BinaryTree tree = new BinaryTree();
        System.out.println("Maximum Depth: " + tree.maxDepth(root)); // 输出最大深度
    }
}

步骤详解

TreeNode类：
- 这是一个树节点类，包含节点值val和左右子节点left和right。
maxDepth方法：
- 检查当前节点是否为空。如果为空，返回0（表示没有深度）。
- 递归计算左子树和右子树的深度。
- 使用Math.max(leftDepth, rightDepth)计算左右子树的最大深度。
- 将最大深度加1（包括当前节点），并返回这个值。
main方法：
- 构造一个示例二叉树。
- 调用maxDepth方法并打印结果。