ความลึกของโหนดระดับคี่ลึกสุดในต้นไม้แบบทวิภาคใน C++

ปัญหา

หาความลึก (Depth) ของโหนดใบ (Leaf Node) ที่อยู่ในระดับคี่ (Odd Level) และลึกที่สุด

อัลกอริธึม

Recursive DFS พร้อมส่ง parameter ระดับปัจจุบัน:

• ถ้าโหนดเป็น NULL → ส่งคืน 0
• เพิ่มระดับปัจจุบัน
• ถ้าเป็นโหนดใบ และระดับเป็นคี่ → ส่งคืนระดับปัจจุบัน
• Recursive ซ้ายและขวา ส่งคืน max ของทั้งสอง

โปรแกรมตัวอย่าง

#include <iostream>
#include <algorithm>
using namespace std;

struct Node {
    int data;
    Node *left, *right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

bool isLeaf(Node* node) {
    return !node->left && !node->right;
}

int deepestOddLevel(Node* node, int level = 0) {
    if (!node) return 0;
    level++;
    if (level % 2 == 1 && isLeaf(node)) return level;
    return max(deepestOddLevel(node->left, level), 
               deepestOddLevel(node->right, level));
}

int main() {
    Node* root = new Node(15);
    root->left = new Node(33);
    root->right = new Node(18);
    root->right->left = new Node(19);
    root->right->right = new Node(20);
    root->right->right->left = new Node(28);
    root->right->right->right = new Node(29);
    
    cout << "Deepest odd level leaf depth: " << deepestOddLevel(root);
    return 0;
}

ผลลัพธ์

Deepest odd level leaf depth: 3