Giả sử chúng ta có một cây tìm kiếm nhị phân cân bằng, chúng ta phải tạo một hàm có tên is_valid_triplet () trả về true khi tồn tại một bộ ba trong BST đã cho có tổng bằng 0, nếu không thì trả về false . Thiết kế phương pháp bằng cách tuân theo các ràng buộc sau -
-
độ phức tạp thời gian dự kiến là O (n ^ 2)
-
Có thể sử dụng thêm dung lượng O (logn).
Vì vậy, nếu đầu vào giống như
thì đầu ra sẽ là True, vì bộ ba là [-15,7,8]
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Xác định một hàm bst_to_doubli_list (), hàm này sẽ lấy root, head, tail,
-
nếu gốc giống như NULL, thì -
-
trở lại
-
-
nếu bên trái của thư mục gốc không rỗng, thì -
-
bst_to_doubli_list (bên trái gốc, đầu, đuôi)
-
-
left of root:=tail
-
nếu đuôi không rỗng, thì -
-
bên phải của đuôi:=root
-
-
Nếu không
-
head:=root
-
-
tail:=root
-
nếu quyền root không rỗng, thì -
-
bst_to_doubli_list (bên phải gốc, đầu, đuôi)
-
-
Xác định một hàm is_in_double_list (), hàm này sẽ lấy đầu, đuôi, tổng,
-
trong khi đầu không bằng đuôi, làm -
-
current:=key of head + key of tail
-
nếu hiện tại bằng tổng, thì -
-
trả về true
-
-
ngược lại khi hiện tại> tổng thì -
-
tail:=left of tail
-
-
Nếu không
-
head:=right of head
-
-
-
trả về false
-
Từ phương thức chính, thực hiện như sau -
-
nếu gốc là null, thì -
-
trả về false
-
-
head =null
-
tail =null
-
bst_to_doubli_list (gốc, đầu, đuôi)
-
while (bên phải của đầu không bằng đuôi và phím của đầu <0), do -
-
if is_in_double (right of head, tail, key of head * (-1), then
-
trả về true
-
-
Nếu không
-
head:=right of head
-
-
-
trả về false
Ví dụ (C ++)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#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);
} Đầu vào
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);
Đầu ra
1