1 问题

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

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

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

示例:

给定二叉树 [3,9,20,null,null,15,7],

返回它的最小深度 2.

2 解法

2.1 递归法

题目中说的是：「最小深度是从根节点到最近叶子节点的最短路径上的节点数量。」，注意是「叶子节点」。
什么是叶子节点，左右孩子都为空的节点才是叶子节点！
所以，如果左子树为空，右子树不为空，说明最小深度是 1 + 右子树的深度。
反之，右子树为空，左子树不为空，最小深度是 1 + 左子树的深度。最后如果左右子树都不为空，返回左右子树深度最小值 + 1 。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int getDepth(TreeNode* node)
    {
        if(node == nullptr)
            return 0;
        int leftDepth = getDepth(node->left);
        int rightDepth = getDepth(node->right);
        //若左子树为空，则树的深度为右子树的深度+1
        if(node->left == nullptr && node->right != nullptr)
            return 1 + rightDepth; 
        //若右子树为空，则树的深度为左子树的深度+1
        if(node->right == nullptr && node->left != nullptr)
            return 1 + leftDepth;

        return 1 + min(leftDepth, rightDepth); 
    }   
    int minDepth(TreeNode* root) {
        return getDepth(root);
    }
};

可以看出：求二叉树的最小深度和求二叉树的最大深度的差别主要在于处理左右孩子不为空的逻辑。

2.2 迭代法

有当左右孩子都为空的时候，才说明遍历的最低点了。如果其中一个孩子为空则不是最低点。

class Solution {
public:

    int minDepth(TreeNode* root) {
        if (root == NULL) return 0;
        int depth = 0;
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty()) {
            int size = que.size(); 
            depth++; // 记录最小深度
            int flag = 0;
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
                if (!node->left && !node->right) { // 当左右孩子都为空的时候，说明是最低点的一层了，退出
                    flag = 1;
                    break;
                }
            }
            if (flag == 1) break;
        }
        return depth;
    }
};