หา Deepest Node ใน Binary Tree ใน C++ (2 วิธี)

ในปัญหานี้ เราได้รับ Binary Tree งานคือหา Deepest Node (node ที่อยู่ระดับลึกที่สุด)

ตัวอย่าง

Output: 8

วิธีที่ 1: Inorder Traversal + Level Tracking O(N)

Recursive traversal เก็บ maxLevel และ deepestNode

void findDeepestRec(Node* root, int level, int& maxLevel, int& deepest) {
    if (!root) return;
    findDeepestRec(root->left, level + 1, maxLevel, deepest);
    if (level > maxLevel) { maxLevel = level; deepest = root->data; }
    findDeepestRec(root->right, level + 1, maxLevel, deepest);
}

int findDeepest(Node* root) {
    int maxLevel = -1, deepest = -1;
    findDeepestRec(root, 0, maxLevel, deepest);
    return deepest;
}

วิธีที่ 2: หาความสูง + หา Node ที่ Level นั้น O(N)

1. คำนวณความสูงของ tree (height)
2. Traverse หา node ที่ level = height

int height(Node* root) {
    if (!root) return 0;
    return 1 + max(height(root->left), height(root->right));
}

void findAtLevel(Node* root, int level) {
    if (!root) return;
    if (level == 1) cout << root->data;
    else {
        findAtLevel(root->left, level - 1);
        findAtLevel(root->right, level - 1);
    }
}

int main() {
    int h = height(root);
    findAtLevel(root, h);
    return 0;
}

ผลลัพธ์

Deepest node: 8