Minimum Depth of Binary Tree trong C++

Tìm độ sâu tối thiểu của cây nhị phân: số nút trên đường đi ngắn nhất từ gốc đến nút lá gần nhất.

Ví dụ: cây [3,9,20,null,null,15,7] → độ sâu min = 2 (đường 3→9).

Giải thuật (BFS)

1. Duyệt theo level (BFS) dùng queue.
2. Level đầu tiên gặp nút lá (không có con) → trả về level đó.

Ví dụ triển khai C++

#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    int minDepth(TreeNode* root) {
        if (!root) return 0;
        queue<TreeNode*> q;
        q.push(root);
        int depth = 0;
        while (!q.empty()) {
            depth++;
            int sz = q.size();
            for (int i = 0; i < sz; i++) {
                TreeNode* cur = q.front(); q.pop();
                if (!cur->left && !cur->right) return depth;
                if (cur->left) q.push(cur->left);
                if (cur->right) q.push(cur->right);
            }
        }
        return depth;
    }
};

// Helper build tree from level-order (0 = null)
TreeNode* build(vector<int> v) {
    if (v.empty() || v[0] == 0) return nullptr;
    TreeNode* root = new TreeNode(v[0]);
    queue<TreeNode*> q;
    q.push(root);
    int i = 1;
    while (!q.empty() && i < v.size()) {
        TreeNode* cur = q.front(); q.pop();
        if (i < v.size() && v[i] != 0) {
            cur->left = new TreeNode(v[i]);
            q.push(cur->left);
        }
        i++;
        if (i < v.size() && v[i] != 0) {
            cur->right = new TreeNode(v[i]);
            q.push(cur->right);
        }
        i++;
    }
    return root;
}

int main() {
    Solution ob;
    vector<int> v = {3,9,20,0,0,15,7};
    cout << ob.minDepth(build(v)); // 2
    return 0;
}

Đầu vào / Đầu ra

Input: {3,9,20,NULL,NULL,15,7}
Output: 2