Java算法题-解析 二叉树的最小深度 算法问题

题目：

给定一个二叉树，找出其最小深度。最小深度是从根节点到最近的叶子节点的最短路径上的节点数量。

引言：

在解决二叉树的问题时，计算最小深度是一个常见的任务。最小深度表示树的最短高度，它可以用于各种应用中，例如确定树的最小高度等。

计算最小深度通常需要使用遍历算法，从根节点开始，递归或使用迭代的方式查找最短路径。

算法思路：

1. 定义一个递归函数 minDepth，该函数接受一个二叉树节点作为参数，并返回该节点的最小深度。
2. 在每个节点上，递归调用 minDepth 函数来计算左子树的最小深度和右子树的最小深度。
3. 如果左子树为空，返回右子树的最小深度加1；如果右子树为空，返回左子树的最小深度加1。
4. 否则，返回左子树和右子树最小深度的较小值加1。

代码实现：

以下是使用 Java 实现的解决方案：

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

public class MinimumDepthOfBinaryTree {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int leftDepth = minDepth(root.left);
        int rightDepth = minDepth(root.right);

        if (leftDepth == 0) {
            return rightDepth + 1;
        }
        if (rightDepth == 0) {
            return leftDepth + 1;
        }

        return Math.min(leftDepth, rightDepth) + 1;
    }

    public static void main(String[] args) {
        MinimumDepthOfBinaryTree solution = new MinimumDepthOfBinaryTree();

        // 创建一个示例二叉树
        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);

        int minDepth = solution.minDepth(root);
        System.out.println("二叉树的最小深度: " + minDepth);
    }
}

算法分析：

• 时间复杂度：对于每个节点，我们只需遍历一次，因此时间复杂度是O(n)，其中n是二叉树的节点数。
• 空间复杂度：递归调用栈的深度最多为树的高度，所以空间复杂度是O(log n)。

示例和测试：

假设给定一个示例二叉树 root，如下所示：

    1
   / \
  2   3
 / \
4   5

根据算法，我们可以计算出这棵树的最小深度是2。我们可以使用以下代码进行测试：

、public class Main {
    public static void main(String[] args) {
        MinimumDepthOfBinaryTree solution = new MinimumDepthOfBinaryTree();

        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);

        int minDepth = solution.minDepth(root);
        System.out.println("二叉树的最小深度: " + minDepth);
    }
}

总结：

计算二叉树的最小深度是一个常见的问题，通过使用递归的方式计算每个节点的左子树和右子树的最小深度，然后取较小值并加1，可以有效地解决这个问题。这个算法的时间复杂度是O(n)，空间复杂度是O(log n)，其中n是二叉树的节点数。解决这个问题有助于理解二叉树的深度性质，以及如何使用递归来处理树结构。