สมมติว่าเรามี balanced binary search tree เราต้องสร้างฟังก์ชันชื่อ is_valid_triplet() ที่คืนค่า true เมื่อมี triplet ใน BST ที่กำหนดซึ่งผลรวมเท่ากับ 0 มิฉะนั้นคืนค่า false ออกแบบวิธีการโดยปฏิบัติตามข้อจำกัดเหล่านี้ −
expected time complexity คือ O(n^2)
O(logn) extra space สามารถใช้ได้
ดังนั้น ถ้า input เป็นแบบ
output จะเป็น True เนื่องจาก triplet คือ [-15,7,8]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ −
กำหนดฟังก์ชัน bst_to_doubli_list() ซึ่งจะรับ root, head, tail
ถ้า root เท่ากับ NULL แล้ว −
คืนค่า
ถ้า left of root ไม่ใช่ null แล้ว −
bst_to_doubli_list(left of root, head, tail)
left of root := tail
ถ้า tail ไม่ใช่ null แล้ว −
right of tail := root
มิฉะนั้น
head := root
tail := root
ถ้า right of root ไม่ใช่ null แล้ว −
bst_to_doubli_list(right of root, head, tail)
กำหนดฟังก์ชัน is_in_double_list() ซึ่งจะรับ head, tail, sum
while head ไม่เท่ากับ tail ให้ทำ −
current := key of head + key of tail
ถ้า current เท่ากับ sum แล้ว −
คืนค่า true
มิฉะนั้นเมื่อ current > sum แล้ว −
tail := left of tail
มิฉะนั้น
head := right of head
คืนค่า false
จาก main method ให้ทำดังนี้ −
ถ้า root เป็น null แล้ว −
คืนค่า false
head = null
tail = null
bst_to_doubli_list(root, head, tail)
while (right of head ไม่เท่ากับ tail และ key of head < 0) ให้ทำ −
ถ้า is_in_double(right of head, tail, key of head * (-1)) แล้ว
คืนค่า true
มิฉะนั้น
head := right of head
คืนค่า false
ตัวอย่าง (C++)
ลองดูการนำไปใช้ต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น −
#include <bits/stdc++.h> using namespace std; class TreeNode { public: int key; TreeNode *left; TreeNode *right; TreeNode() : key(0), left(NULL), right(NULL) {} TreeNode(int x) : key(x), left(NULL), right(NULL) {} }; void bst_to_doubli_list(TreeNode* root, TreeNode** head, TreeNode** tail) { if (root == NULL) return; if (root->left) bst_to_doubli_list(root->left, head, tail); root->left = *tail; if (*tail) (*tail)->right = root; else *head = root; *tail = root; if (root->right) bst_to_doubli_list(root->right, head, tail); } bool is_in_double_list(TreeNode* head, TreeNode* tail, int sum) { while (head != tail) { int current = head->key + tail->key; if (current == sum) return true; else if (current > sum) tail = tail->left; else head = head->right; } return false; } bool is_valid_triplet(TreeNode *root) { if (root == NULL) return false; TreeNode* head = NULL; TreeNode* tail = NULL; bst_to_doubli_list(root, &head, &tail); while ((head->right != tail) && (head->key < 0)){ if (is_in_double_list(head->right, tail, -1*head->key)) return true; else head = head->right; } return false; } TreeNode* insert(TreeNode* root, int key) { if (root == NULL) return new TreeNode(key); if (root->key > key) root->left = insert(root->left, key); else root->right = insert(root->right, key); return root; } int main(){ TreeNode* root = NULL; root = insert(root, 7); root = insert(root, -15); root = insert(root, 15); root = insert(root, -7); root = insert(root, 14); root = insert(root, 16); root = insert(root, 8); cout << is_valid_triplet(root); }อินพุต
root = insert(root, 7); root = insert(root, -15); root = insert(root, 15); root = insert(root, -7); root = insert(root, 14); root = insert(root, 16); root = insert(root, 8);
เอาต์พุต
1
