算法

(DFS) $O(n)$

• 这道题与 104. 二叉树的最大深度 题面非常相似，但需要多思考一步。
• 我们知道，在求最大深度时，递归条件是：每个节点的深度等于其左右子树最大深度值加上 1。在求最小深度时，如果类比过来，令每个节点的深度等于其左右子树最小深度值加上 1，这样做是不对的。以tree = {1,2,#,3}为例，这是三层的树，最小深度应该是3，但如果按照上述做法，节点1的右子树为空，我们会得出节点1的最小深度是1的结论，跟答案不符。
• 正确做法是要判断一下左右子树是否有空子树，如果有，那么最小深度等于另一颗子树的深度加1。

C++ 代码

class Solution {
public:
    int minDepth(TreeNode* root) {
        if (root == nullptr) return 0;

        int leftDepth = minDepth(root->left);
        int rightDepth = minDepth(root->right);

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

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