二叉树的最小深度

方法一：递归法

class Solution {
public:
    int minDepth(TreeNode* root) {
        int height = 0;
        if (root == nullptr) {
            return height;
        }
        if (root->left == nullptr && root->right != nullptr) {
            return minDepth(root->right) + 1;
        }
        if (root->left != nullptr && root->right == nullptr) {
            return minDepth(root->left) + 1;
        }
        return min(minDepth (root->right), minDepth (root->left) ) + 1;
    }
};

注意：因为要确定的是叶子到根的最小距离，所以要去掉不是叶子到根的距离。

方法二：（层序遍历）迭代法

class Solution {
public:
    int minDepth(TreeNode* root) {
        queue que;
        if (root != nullptr) {
            que.push(root);
        }
        int depth = 0;
        while (!que.empty()) {
            int size = que.size();
            depth++;
            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 == nullptr && node->right == nullptr) {
                    return depth;
                }
            }
        }
        return depth;
    }
};

思路：在层序遍历的时候第一个遇到的叶子结点就是最短距离的那一层。其实就是看那一层先出现叶子结点。