111. 二叉树的最小深度

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

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

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

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：2

示例 2：

输入：root = [2,null,3,null,4,null,5,null,6]
输出：5

提示：

• 树中节点数的范围在 [0, 10^5] 内
• -1000 <= Node.val <= 1000

非空节点只有两类，叶子节点和非叶子节点。

DFS-自底向上-动态规划-后序遍历，归并，有返回值无辅助参数的DFS

首先可以想到使用深度优先搜索的方法，遍历整棵树，记录最小深度。

对于每一个非叶子节点，我们只需要分别计算其左右子树的最小叶子节点深度。这样就将一个大问题转化为了小问题，可以递归地解决该问题。

class Solution {
    public int minDepth(TreeNode root) {
        // 当前节点要么为空，要么不为空，不为空时要么是叶子节点，要么不是。
        // 如果根节点为空，直接返回 0，表示空树的深度为 0。这行不能删，为了处理输入空数组的情况。
        if (root == null) {
            return 0;
        }
        // 如果根节点没有左孩子和右孩子，说明是叶子节点，直接返回 1。
        // 下面两个if都不是叶子节点的情况，因此当递归前进到叶子节点时，哪个if都进不去，
        // 最后返回Integer.MAX_VALUE+1.这就出错了，因此一定要处理叶子节点。
        // 处理了叶子节点，为什么还要处理root为空的情况呢？因为有可能输入的root就是空，不是经过叶子节点到达的。
        if (root.left == null && root.right == null) {
            return 1;
        }

        // 初始化最小深度为一个很大的值，用于后续比较
        int min_depth = Integer.MAX_VALUE;
        // 如果左孩子不为空，递归计算左子树的最小深度
        // 如果子树为空，则不能计算，不然min_depth就是0了。重点。
        if (root.left != null) {
            min_depth = Math.min(minDepth(root.left), min_depth);
        }
        // 如果右孩子不为空，递归计算右子树的最小深度。
        if (root.right != null) {
            min_depth = Math.min(minDepth(root.right), min_depth);
        }

        // 返回最小深度加 1（包括当前根节点）
        return min_depth + 1;
    }
}

为什么下面这样做不行？因为如果root.left是空，root.right不是空，则这样算出来的min_depth是0，而此时它应该是右子树的最小深度。因此如果要记录子节点的最小深度，则需要子节点不为空。现在问题来了，怎么处理左右子节点都是null的情况呢？那就是叶子节点了，直接返回1即可。

class Solution {
    public int minDepth(TreeNode root) {
        // 如果根节点为空，直接返回 0，表示空树的深度为 0
        if (root == null) {
            return 0;
        }

        // 初始化最小深度为一个很大的值，用于后续比较
        int min_depth = Integer.MAX_VALUE;

        // 递归计算左子树的最小深度
        min_depth = Math.min(minDepth(root.left), min_depth);
        // 递归计算右子树的最小深度
        min_depth = Math.min(minDepth(root.right), min_depth);

        // 返回最小深度加 1（包括当前根节点）
        return min_depth + 1;
    }
}

如果想实现先无条件进入子递归，再检查是否为空，可以这么写：

class Solution {
    public int minDepth(TreeNode root) {
        // 如果根节点为空，直接返回 0
        if (root == null) {
            return 0;
        }

        // 递归计算左子树和右子树的最小深度
        int leftDepth = minDepth(root.left);
        int rightDepth = minDepth(root.right);

        // 如果当前节点是叶子节点，直接返回 1
        if (root.left == null && root.right == null) {
            return 1;
        }
        // 如果左子树为空，则只考虑右子树的深度
        if (root.left == null) {
            return rightDepth + 1;
        }
        // 如果右子树为空，则只考虑左子树的深度
        if (root.right == null) {
            return leftDepth + 1;
        }

        // 如果左右子树都不为空，取二者的最小深度加 1
        return Math.min(leftDepth, rightDepth) + 1;
    }
}

• 时间复杂度：O(N)，其中 N 是树的节点数。对每个节点访问一次。
• 空间复杂度：O(H)，其中 H 是树的高度。空间复杂度主要取决于递归时栈空间的开销，最坏情况下，树呈现链状，空间复杂度为 O(N)。平均情况下树的高度与节点数的对数正相关，空间复杂度为 O(log⁡N)。

BFS

当我们找到一个叶子节点时，直接返回这个叶子节点的深度。广度优先搜索的性质保证了最先搜索到的叶子节点的深度一定最小。

class Solution {
    // 定义一个队列节点类，包含树节点和其深度
    class QueueNode {
        TreeNode node;
        int depth;

        // 构造函数，初始化节点和深度
        public QueueNode(TreeNode node, int depth) {
            this.node = node;
            this.depth = depth;
        }
    }

    public int minDepth(TreeNode root) {
        // 如果根节点为空，直接返回0，表示空树的深度为0
        if (root == null) {
            return 0;
        }

        // 使用队列进行广度优先搜索（BFS）
        Queue<QueueNode> queue = new LinkedList<>();
        // 将根节点及其深度（1）加入队列
        queue.offer(new QueueNode(root, 1));
        
        // 当队列不为空时，进行循环
        while (!queue.isEmpty()) {
            // 取出队首节点
            QueueNode nodeDepth = queue.poll();
            TreeNode node = nodeDepth.node; // 当前节点
            int depth = nodeDepth.depth; // 当前节点的深度

            // 结束条件：如果当前节点是叶子节点，直接返回其深度。
            // 第一个叶子节点对应的深度就是最小深度。提前结束。重点。
            if (node.left == null && node.right == null) {
                return depth;
            }

            // 如果左子节点不为空，将其加入队列，并且深度加1
            if (node.left != null) {
                queue.offer(new QueueNode(node.left, depth + 1));
            }
            // 如果右子节点不为空，将其加入队列，并且深度加1，注意左右子节点的深度是相等的。
            if (node.right != null) {
                queue.offer(new QueueNode(node.right, depth + 1));
            }
        }

        // 理论上不会到达这里，因为会在找到叶子节点时返回
        return 0;
    }
}

• 时间复杂度：O(N)，其中 N 是树的节点数。对每个节点访问一次。
• 空间复杂度：O(N)，其中 N 是树的节点数。空间复杂度主要取决于队列的开销，队列中的元素个数不会超过树的节点数。

自顶向下-前序遍历。无返回值有辅助参数的DFS

class Solution {
    // 用于存储最小深度的变量，初始化为最大值
    private int ans = Integer.MAX_VALUE;

    public int minDepth(TreeNode root) {
        // 如果根节点为空，返回0
        if (root == null) {
            return 0;
        }
        // 调用深度优先搜索（DFS）方法
        dfs(root, 1);
        // 返回计算出的最小深度
        return ans;
    }

    // 深度优先搜索（DFS）方法，递归计算树的深度
    private void dfs(TreeNode node, int depth) {
        // 如果节点为空，直接返回。这行代码不能删，因为null未必一定在叶子节点之后，例如root的左子节点不为空，右子节点为空，则root不是叶子节点，从而我们遍历完它的左子树后会进入它的右子树，然后右子节点是null，从而node.left会报空指针异常。
        if (node == null) {
            return;
        }
        // 如果当前节点是叶子节点，更新最小深度，返回。
        if (node.left == null && node.right == null) {
            ans = Math.min(ans, depth);
            return;
        }
        
        // 如果不是叶子结点，则递归处理左子节点，深度加 1
        dfs(node.left, depth + 1);
        // 递归处理右子节点, 深度加 1
        dfs(node.right, depth + 1);
    }
}