หาความลึกน้อยที่สุดของ Binary Tree ใน C++

คำอธิบายปัญหา

ได้รับ Binary Tree (ต้นไม้แบบทวิภาค) ซึ่งแต่ละโหนดมีลูกได้สูงสุด 2 ตัว ต้องการหา ความลึกน้อยที่สุด (Minimum Depth) ของต้นไม้

นิยาม: Minimum Depth คือ เส้นทางสั้นที่สุด จากโหนดราก (Root) ไปยังโหนดใบ (Leaf Node) ใดๆ

ตัวอย่าง

Output: 2

แนวทางที่ 1: Recursive DFS (Depth-First Search)

ใช้ Recursion ไปที่ลูกของแต่ละโหนด:

• ถ้าโหนดเป็น NULL → คืนค่า 0
• ถ้าเป็น Leaf (ไม่มีลูกทั้งคู่) → คืนค่า 1
• ถ้ามีลูกข้างเดียว → คำนวณความลึกของข้างที่มีลูก + 1
• ถ้ามีลูกทั้งสองข้าง → คืนค่า min(leftDepth, rightDepth) + 1

โค้ด C++ (Recursive)

#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 << "The minimum depth of binary tree is " << findMinDepthBT(root);
    return 0;
}

แนวทางที่ 2: Level Order Traversal (BFS) - มีประสิทธิภาพมากกว่า

ใช้ Queue ทำ Level Order Traversal (BFS) ไปทีละระดับ เมื่อเจอ Leaf Node แรก → คืนค่าระดับนั้นทันที (เพราะ BFS จะเจอเส้นทางสั้นที่สุดก่อน)

โค้ด C++ (BFS)

#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;
}

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 << "The minimum depth of binary tree is " << findMinDepthBT(root);
    return 0;
}

ผลลัพธ์

The minimum depth of binary tree is 2

สรุป:

วิธี BFS (Level Order) มีประสิทธิภาพดีกว่า Recursive DFS เพราะหยุดได้ทันทีเมื่อเจอ Leaf แรก ไม่ต้อง遍歷ต้นไม้ทั้งหมด