home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

Largest BST Subtree ใน C++

สมมติว่ามี binary tree เราต้องหาสับทรีที่ใหญ่ที่สุดของมัน โดยใหญ่ที่สุดหมายถึงสับทรีที่มีจำนวนโหนดมากที่สุด

เช่น ถ้าอินพุทเป็นแบบ

Largest BST Subtree ใน C++

ผลลัพธ์จะเป็น 3 เนื่องจาก Largest BST Subtree ในกรณีนี้คือส่วนที่ไฮไลท์

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนดังนี้ −

  • กำหนดโครงสร้างชื่อ Data มี 4 ค่า: size, maxVal, minVal, และ ok (ok เก็บได้แค่ true/false)

  • solve(TreeNode * node)

  • ถ้า node เป็น null แล้ว −

    • คืนค่า Data โดยเริ่มต้น (0, infinity, -infinity, true)

  • left := solve(left ของ node)

  • right := solve(right ของ node)

  • กำหนด Data ชื่อ curr

  • curr.ok := false

  • ถ้าค่าของ node >= right.minVal แล้ว −

    • คืนค่า curr

  • ถ้าค่าของ node <= left.maxVal แล้ว −

    • คืนค่า curr

  • ถ้า left.ok เป็น true และ right.ok เป็น true แล้ว −

    • curr.sz := 1 + left.sz + right.sz

    • curr.ok := true

    • curr.maxVal := สูงสุดของ (ค่าของ node และ right.maxVal)

    • curr.minVal := ต่ำสุดของ (ค่าของ node และ left.minVal)

  • ถ้า curr.ok เป็น true แล้ว −

    • ret := สูงสุดของ ret และ curr.sz

    • คืนค่า curr

  • จากเมธอดหลัก ทำดังนี้ −

  • ret := 0

  • solve(root)

  • คืนค่า ret

ตัวอย่าง

ลองดูการติดตั้งต่อไปนี้เพื่อให้เข้าใจได้ดีขึ้น −

#include <bits/stdc++.h> using namespace std; class TreeNode{ public:    int val;    TreeNode *left, *right;    TreeNode(int data){       val = data;       left = NULL;       right = NULL;    } }; void insert(TreeNode **root, int val){    queue<TreeNode*> q;    q.push(*root);    while(q.size()){       TreeNode *temp = q.front();       q.pop();       if(!temp->left){          if(val != NULL)             temp->left = new TreeNode(val);          else             temp->left = new TreeNode(0);          return;       }       else{          q.push(temp->left);       }       if(!temp->right){          if(val != NULL)             temp->right = new TreeNode(val);          else             temp->right = new TreeNode(0);          return;       }       else{          q.push(temp->right);       }    } } TreeNode *make_tree(vector<int> v){    TreeNode *root = new TreeNode(v[0]);    for(int i = 1; i<v.size(); i++){       insert(&root, v[i]);    }    return root; } struct Data{    int sz;    int maxVal;    int minVal;    bool ok;    Data(){}    Data(int a, int b, int c, bool d){       sz = a;       minVal = b;       maxVal = c;       ok = d;    } }; class Solution { public:    int ret;    Data solve(TreeNode* node){       if (!node)          return Data(0, INT_MAX, INT_MIN, true);       Data left = solve(node->left);       Data right = solve(node->right);       Data curr;       curr.ok = false;       if (node->val >= right.minVal) {          return curr;       }       if (node->val <= left.maxVal) {          return curr;       }       if (left.ok && right.ok) {          curr.sz = 1 + left.sz + right.sz;          curr.ok = true;          curr.maxVal = max(node->val, right.maxVal);          curr.minVal = min(node->val, left.minVal);       }       if (curr.ok)          ret = max(ret, curr.sz);       return curr;    }    int largestBSTSubtree(TreeNode* root){       ret = 0;       solve(root);       return ret;    } }; main(){    Solution ob;    vector<int> v = {10,5,15,1,8,NULL,7};    TreeNode *root= make_tree(v);    cout << (ob.largestBSTSubtree(root)); }

อินพุท

[10,5,15,1,8,null,7]

เอาต์พุท

3