หาความลึกของโหนดระดับคี่ลึกที่สุดใน Binary Tree ใน C++

บทนำ

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

ขั้นตอนการแก้ปัญหา

1. สร้าง Binary Tree ด้วยข้อมูลตัวอย่าง
2. เขียนฟังก์ชัน Recursive รับพารามิเตอร์ root และ level ปัจจุบัน
3. ถ้าเป็นโหนดใบ (left=null, right=null) และ level เป็นคี่ → คืนค่า level
4. มิฉะนั้น → คืนค่า max ของ recursive call ลูกซ้ายและลูกขวา (level+1)
5. ถ้าไม่มีโหนดใบระดับคี่ → คืน 0

ตัวอย่างโค้ด

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

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

struct Node* newNode(int data) {
    struct Node* node = (struct Node*) malloc(sizeof(struct Node));
    node->data = data;
    node->left = node->right = NULL;
    return node;
}

int oddLeafDepthInTree(struct Node *root, int level) {
    if (root == NULL) {
        return 0;
    }
    if (root->left == NULL && root->right == NULL && level % 2 == 1) {
        return level;
    }
    return max(oddLeafDepthInTree(root->left, level + 1), oddLeafDepthInTree(root->right, level + 1));
}

int main() {
    struct Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->right->left = newNode(5);
    root->right->right = newNode(6);
    root->right->left->right = newNode(7);
    root->right->right->right = newNode(8);
    int level = 1, depth = 0;
    cout << oddLeafDepthInTree(root, level) << endl;
    return 0;
}

ผลลัพธ์

3

คำอธิบายต้นไม้ตัวอย่าง

        1 (level 1)
       / \
      2   3 (level 2)
     /   / \
    4   5   6 (level 3)
       /     \
      7       8 (level 4)

โหนดใบระดับคี่: 4 (level 3) → ลึกที่สุด = 3

สรุป

ปรับแต่งจากการหาความลึกปกติ เพิ่มเงื่อนไข level % 2 == 1 และตรวจสอบ leaf node ใช้ได้กับโจทย์ Tree Traversal แบบมีเงื่อนไข