C++에서 0에 더해지는 균형 BST에 트리플렛이 있는지 찾기

균형 이진 검색 트리가 있다고 가정하고 주어진 BST에 합이 0인 삼중항이 있으면 true를 반환하고 그렇지 않으면 false를 반환하는 is_valid_triplet()이라는 함수를 만들어야 합니다. . 다음 제약 조건에 따라 방법을 설계하십시오 -

예상 시간 복잡도는 O(n^2)
O(logn) 추가 공간을 사용할 수 있습니다.

입력이 다음과 같으면

트리플렛은 [-15,7,8]

이므로 출력은 True가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

bst_to_doubli_list() 함수를 정의하면 루트, 헤드, 테일,
루트가 NULL과 같으면 -
- 반환
루트의 왼쪽이 null이 아니면 -
- bst_to_doubli_list(루트, 머리, 꼬리의 왼쪽)
루트 왼쪽 :=꼬리
꼬리가 null이 아니면 -
- 꼬리 오른쪽 :=루트
그렇지 않으면
- 머리 :=루트
꼬리 :=루트
루트의 오른쪽이 null이 아니면 -
- bst_to_doubli_list(루트, 머리, 꼬리의 오른쪽)
is_in_double_list() 함수를 정의합니다. 이것은 head, tail, sum,
를 취합니다.
머리가 꼬리와 같지 않은 동안 −
- 현재 :=머리의 키 + 꼬리의 키
- 전류가 합과 같으면 -
  - true를 반환
- 그렇지 않으면 현재> 합계일 때 -
  - 꼬리 :=꼬리의 왼쪽
- 그렇지 않으면
  - 머리 :=머리 오른쪽
거짓을 반환
기본 방법에서 다음을 수행하십시오 -
루트가 null이면 -
- 거짓을 반환
머리 =null
꼬리 =null
bst_to_doubli_list(루트, 헤드, 테일)
동안 (머리의 오른쪽이 꼬리와 같지 않고 머리의 키 <0), −
- if is_in_double(머리 오른쪽, 꼬리, 머리 키 * (-1), then
  - true를 반환
- 그렇지 않으면
  - 머리 :=머리 오른쪽
거짓을 반환

예시(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);