Continuous Tree ใน C++

Continuous Tree นิยามว่าเป็นต้นไม้ที่ทุกเส้นทางจากราก (root) ไปยังใบ (leaf) มีค่าน้ำหนักของโหนดที่ทำให้ ความต่างสัมบูรณ์ระหว่างโหนดพาเรนต์กับลูกโดยตรงทุกตัวเท่ากับ 1 เสมอ

หากเลือกโหนดใดบนเส้นทางจากรากถึงใบ:

• |weight(node) - weight(left child)| = 1
• |weight(node) - weight(right child)| = 1

ตัวอย่างภาพ

ต้นไม้ด้านล่างเป็น Continuous Tree เพราะความต่างสัมบูรณ์ระหว่างพาเรนต์และลูกเป็น 1 เสมอ:

ต้นไม้ด้านล่าง ไม่ใช่ Continuous Tree:

อัลกอริทึมตรวจสอบ Continuous Tree

1. ถ้า root เป็น NULL → คืนค่า 1 (true)
2. ถ้าเป็น Leaf node → คืนค่า 1 (เพราะเส้นทางนี้ Continuous จนถึงที่นี่)
3. ถ้าไม่มีลูกซ้าย → ตรวจสอบความต่างกับลูกขวา และเรียกซ้ำ subtree ขวา
4. ถ้าไม่มีลูกขวา → ตรวจสอบความต่างกับลูกซ้าย และเรียกซ้ำ subtree ซ้าย
5. กรณีทั่วไป → ตรวจสอบความต่างกับทั้งสองลูก และเรียกซ้ำทั้งสอง subtree

Pseudocode

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

int isContinuous(btreeNode *root) {
    if (root == NULL)
        return 1;
    if (root->left == NULL && root->right == NULL)
        return 1;
    if (root->left == NULL)
        return (abs(root->data - root->right->data) == 1) && isContinuous(root->right);
    if (root->right == NULL)
        return (abs(root->data - root->left->data) == 1) && isContinuous(root->left);
    return abs(root->data - root->left->data) == 1 &&
           abs(root->data - root->right->data) == 1 &&
           isContinuous(root->left) && isContinuous(root->right);
}

Complexity: Time O(n), Space O(h) โดย h = ความสูงของต้นไม้ (stack recursion)