数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装学
法学在 C++ 中查找平衡 BST 中是否存在三元组加起来等于零
假设我们有一个平衡的二叉搜索树，我们需要创建一个名为 `is_valid_triplet()` 的函数，当给定 BST 中存在一个三元组的和等于 0 时返回 `true`，否则返回 `false`。请根据以下约束设计此方法：
预期时间复杂度为 O(n^2)
可以使用 O(logn) 的额外空间。
因此，如果输入如下所示：
则输出将为 True，因为三元组为 [-15,7,8]
为了解决这个问题，我们将遵循以下步骤：
定义一个函数 `bst_to_doubli_list()`，它将接收根节点、头节点和尾节点。
如果根节点为空，则：
返回
如果根节点的左子节点不为空，则：
bst_to_doubli_list(根节点的左子节点, 头节点, 尾节点)
根节点的左子节点 := 尾节点
如果尾节点不为空，则：
尾节点的右子节点 := 根节点
否则
头节点 := 根节点
尾节点 := 根节点
如果根节点的右子节点不为空，则：
bst_to_doubli_list(根节点的右子节点, 头节点, 尾节点)
定义一个函数 `is_in_double_list()`，它将接收头节点、尾节点和总和。
当头节点不等于尾节点时，执行以下操作：
当前值 := 头节点的值 + 尾节点的值
如果当前值等于总和，则：
返回 true
否则，如果当前值 > 总和，则：
尾节点 := 尾节点的左子节点
否则
头节点 := 头节点的右子节点
返回 false
在主方法中，执行以下操作：
如果根节点为空，则：
返回 false
头节点 = 空
尾节点 = 空
bst_to_doubli_list(根节点, 头节点, 尾节点)
当 (头节点的右子节点不等于尾节点且头节点的值 < 0) 时，执行以下操作：
如果 is_in_double(头节点的右子节点, 尾节点, 头节点的值 * (-1))，则
返回 true
否则
头节点 := 头节点的右子节点
返回 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
159 次浏览
