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

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

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

示例 1：

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

示例 2：

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

提示：

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

Solution

参考 BFS 算法解题套路框架 、代码随想录

• BFS 算法，本质还是层序遍历

# @lc code=start
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if not root: return 0
        
        que = collections.deque([(root, 1)])
        while que:
            node, depth = que.popleft()
            if not node.left and not node.right:
                return depth
            if node.left:
                que.append((node.left, depth+1))
            if node.right:
                que.append((node.right, depth+1))
        return depth
# @lc code=end

cpp

class Solution {
public:
    int minDepth(TreeNode* root) {
        if(root==nullptr) return 0;
        
        queue<pair<TreeNode*, int>> q;
        q.emplace(root,1);
        while(!q.empty()){
            TreeNode* cur = q.front().first;
            int depth = q.front().second;
            q.pop();

            if(cur->left==nullptr && cur->right==nullptr)
                return depth;
            if(cur->left != nullptr)
                q.emplace(cur->left, depth+1);
            if(cur->right != nullptr)
                q.emplace(cur->right, depth+1);
        }
        return 0;
    }
};

• 迭代法，层序遍历

class Solution {
public:
    int minDepth(TreeNode* root) {
        if(root==nullptr) return 0;
        
        int depth = 0;
        queue<TreeNode *> que;
        que.push(root);
        while (!que.empty()) {
            int n = que.size();
            depth++;
            int flag = 0; //标记是否有叶子节点出现
            for (int i = 0; i < n; ++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;
    }
};

• DFS 算法，后序遍历
• 右子树为空，左子树不为空，最小深度是 1 + 左子树的深度。最后如果左右子树都不为空，返回左右子树深度最小值 + 1 。

class Solution {
public:
    int getDepth(TreeNode* node) {
        if (node == NULL) return 0;
        int leftDepth = getDepth(node->left);    // 左
        int rightDepth = getDepth(node->right);  // 右
                                                 // 中
        // 当一个左子树为空，右不为空，这时并不是最低点
        if (node->left == NULL && node->right != NULL) { 
            return 1 + rightDepth;
        }   
        // 当一个右子树为空，左不为空，这时并不是最低点
        if (node->left != NULL && node->right == NULL) { 
            return 1 + leftDepth;
        }
        int result = 1 + min(leftDepth, rightDepth); 
        return result;
    }

    int minDepth(TreeNode* root) {
        return getDepth(root);
    }
};

java

class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftDepth = minDepth(root.left);
        int rightDepth = minDepth(root.right);
        if (root.left == null) {
            return rightDepth + 1;
        }
        if (root.right == null) {
            return leftDepth + 1;
        }
        return Math.min(leftDepth, rightDepth) + 1;
    }
}