Tìm độ sâu nhỏ nhất của cây nhị phân trong C++

Mô tả vấn đề

Cho một cây nhị phân (mỗi nút có tối đa 2 con). Nhiệm vụ là tìm độ sâu nhỏ nhất (minimum depth) của cây nhị phân.

Độ sâu nhỏ nhất là đường đi ngắn nhất từ nút gốc (root) đến bất kỳ nút lá (leaf) nào.

Ví dụ minh họa

Đầu vào: Cây nhị phân như hình minh họa

Đầu ra:

2

Phương pháp giải quyết

Cách 1: Đệ quy (DFS)

• Nếu nút là NULL, trả về 0
• Nếu nút là lá (không có con trái và phải), trả về 1
• Nếu chỉ có con phải, đệ quy con phải + 1
• Nếu chỉ có con trái, đệ quy con trái + 1
• Ngược lại, trả về min(đệ quy trái, đệ quy phải) + 1

Cách 2: Duyệt theo cấp độ (BFS/Level Order) - Hiệu quả hơn

Duyệt cây theo từng cấp độ. Trả về số cấp độ khi gặp nút lá đầu tiên. Cách này dừng sớm hơn so với DFS khi tìm độ sâu nhỏ nhất.

Chương trình minh họa (Cách 1 - Đệ quy)

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

struct Node {
    int data;
    struct Node *left, *right;
};

int findMinDepthBT(Node *currentNode) {
    if (currentNode == NULL)
        return 0;
    if (currentNode->left == NULL && currentNode->right == NULL)
        return 1;
    if (!currentNode->left)
        return findMinDepthBT(currentNode->right) + 1;
    if (!currentNode->right)
        return findMinDepthBT(currentNode->left) + 1;
    return min(findMinDepthBT(currentNode->left),
               findMinDepthBT(currentNode->right)) + 1;
}

Node *newNode(int data) {
    Node *temp = new Node;
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}

int main() {
    Node *root = newNode(5);
    root->left = newNode(2);
    root->right = newNode(9);
    root->left->left = newNode(5);
    root->left->right = newNode(1);
    root->left->left->left = newNode(7);
    root->left->left->right = newNode(3);
    cout << "Độ sâu nhỏ nhất của cây nhị phân là " << findMinDepthBT(root);
    return 0;
}

Chương trình minh họa (Cách 2 - BFS/Level Order)

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

struct Node {
    int data;
    struct Node *left, *right;
};

struct lOrderQueue {
    Node *node;
    int depth;
};

int findMinDepthBT(Node *root) {
    if (root == NULL)
        return 0;
    queue<lOrderQueue> levelOrder;
    lOrderQueue deQueue = {root, 1};
    levelOrder.push(deQueue);
    while (!levelOrder.empty()) {
        deQueue = levelOrder.front();
        levelOrder.pop();
        Node *node = deQueue.node;
        int depth = deQueue.depth;
        if (node->left == NULL && node->right == NULL)
            return depth;
        if (node->left != NULL) {
            deQueue.node = node->left;
            deQueue.depth = depth + 1;
            levelOrder.push(deQueue);
        }
        if (node->right != NULL) {
            deQueue.node = node->right;
            deQueue.depth = depth + 1;
            levelOrder.push(deQueue);
        }
    }
    return 0;
}

// main() tương tự cách 1

Kết quả đầu ra

Độ sâu nhỏ nhất của cây nhị phân là 2