题解 | #二叉树的最小深度#基于bfs

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 * };
 */

class Solution {
  public:
    /**
     *
     * @param root TreeNode类
     * @return int整型
     */
    int run(TreeNode* root) {
        if (root == nullptr) return 0;

        // 使用队列进行层次遍历
        queue<TreeNode*> q;
        q.push(root);
        int depth = 1; // 根节点的深度为1

        while (!q.empty()) {
            int levelSize = q.size(); // 当前层的节点数
            for (int i = 0; i < levelSize; ++i) {
                TreeNode* node = q.front();
                q.pop();

                // 如果当前节点是叶子节点，返回当前深度
                if (node->left == nullptr && node->right == nullptr) {
                    return depth;
                }

                // 将当前节点的子节点加入队列
                if (node->left != nullptr) {
                    q.push(node->left);
                }
                if (node->right != nullptr) {
                    q.push(node->right);
                }
            }
            depth++; // 每处理完一层，深度加1
        }

        return depth; // 理论上不会到达这里
    }
};