นับจำนวน Binary Search Trees (BST) ใน Binary Tree ด้วย C++

โจทย์: ให้ Binary Tree ต้องการนับจำนวน Subtree ที่เป็น Binary Search Tree (BST) โดย BST หมายถึง ต้นไม้ที่โหนดซ้าย < โหนดแม่ < โหนดขวา

แนวคิด: Bottom-up Traversal

เดินต้นไม้จากใบขึ้นมาสู่ราก สำหรับแต่ละโหนด ตรวจสอบว่า Subtree ที่รากที่โหนดนั้นเป็น BST หรือไม่ โดยใช้ข้อมูลจากลูกซ้ายและลูกขวา

โครงสร้างข้อมูลสำหรับส่งค่ากลับ

struct node_data {
    int total_bst;    // จำนวน BST ใน subtree นี้
    int highest;      // ค่าสูงสุดใน subtree
    int lowest;       // ค่าต่ำสุดใน subtree
    bool check;       // true ถ้า subtree นี้เป็น BST
};

ฟังก์ชันหลัก

node_data BST_present(struct tree_node* parent) {
    if (parent == NULL) {
        return { 0, INT_MAX, INT_MIN, true };  // empty tree เป็น BST
    }
    
    if (parent->left == NULL && parent->right == NULL) {
        return { 1, parent->data, parent->data, true };  // ใบเป็น BST
    }
    
    node_data Left = BST_present(parent->left);
    node_data Right = BST_present(parent->right);
    
    node_data n1;
    n1.lowest = min(parent->data, min(Left.lowest, Right.lowest));
    n1.highest = max(parent->data, max(Left.highest, Right.highest));
    
    // ตรวจสอบเงื่อนไข BST
    if (Left.check && Right.check && 
        parent->data > Left.highest && 
        parent->data < Right.lowest) {
        n1.check = true;
        n1.total_bst = 1 + Left.total_bst + Right.total_bst;
    } else {
        n1.check = false;
        n1.total_bst = Left.total_bst + Right.total_bst;
    }
    
    return n1;
}

ตัวอย่างเต็ม

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

struct tree_node {
    struct tree_node* left;
    struct tree_node* right;
    int data;
    tree_node(int data) {
        this->data = data;
        this->left = NULL;
        this->right = NULL;
    }
};

struct node_data {
    int total_bst;
    int highest, lowest;
    bool check;
};

node_data BST_present(struct tree_node* parent) {
    if (parent == NULL) {
        return { 0, INT_MAX, INT_MIN, true };
    }
    if (parent->left == NULL && parent->right == NULL) {
        return { 1, parent->data, parent->data, true };
    }
    node_data Left = BST_present(parent->left);
    node_data Right = BST_present(parent->right);
    node_data n1;
    n1.lowest = min(parent->data, min(Left.lowest, Right.lowest));
    n1.highest = max(parent->data, max(Left.highest, Right.highest));
    if (Left.check && Right.check && parent->data > Left.highest && parent->data < Right.lowest) {
        n1.check = true;
        n1.total_bst = 1 + Left.total_bst + Right.total_bst;
    } else {
        n1.check = false;
        n1.total_bst = Left.total_bst + Right.total_bst;
    }
    return n1;
}

int main() {
    struct tree_node* root = new tree_node(3);
    root->left = new tree_node(7);
    root->right = new tree_node(4);
    root->left->left = new tree_node(5);
    root->right->right = new tree_node(1);
    root->left->left->left = new tree_node(10);
    
    cout << "Count the Number of Binary Search Trees present in a Binary Tree are: "
         << BST_present(root).total_bst;
    return 0;
}

ผลลัพธ์

Count the Number of Binary Search Trees present in a Binary Tree are: 2

ความซับซ้อน: Time O(n), Space O(h) โดย h คือความสูงของต้นไม้