数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究在 C++ 中查找平衡 BST 中具有给定和的配对
假设我们有一个平衡的二叉搜索树和一个目标和，我们需要定义一个方法来检查它是否是一对和等于目标和，或者不是。在这种情况下。我们需要记住二叉搜索树是不可变的。
因此，如果输入类似于
那么输出将是 (9 + 26 = 35)
为了解决这个问题，我们将遵循以下步骤 -
- 定义栈 s1、s2
- done1 := false，done2 := false
- val1 := 0，val2 := 0
- curr1 := 根节点，curr2 := 根节点
- 无限循环，执行 -
- 当 done1 为 false 时，执行 -
- 如果 curr1 不等于 NULL，则 -
- 将 curr1 插入 s1
- curr1 := curr1 的左子节点
- 否则
- 如果 s1 为空，则 -
- done1 := 1
- 否则
- curr1 := s1 的顶部元素
- 从 s1 中删除元素
- val1 := curr1 的值
- curr1 := curr1 的右子节点
- done1 := 1
- 如果 s1 为空，则 -
- 如果 curr1 不等于 NULL，则 -
- 当 done2 为 false 时，执行 -
- 如果 curr2 不等于 NULL，则 -
- 将 curr2 插入 s2
- curr2 := curr2 的右子节点
- 否则
- 如果 s2 为空，则 -
- done2 := 1
- 如果 s2 为空，则 -
- 否则
- curr2 := s2 的顶部元素
- 从 s2 中删除元素
- val2 := curr2 的值
- curr2 := curr2 的左子节点
- done2 := 1
- 如果 curr2 不等于 NULL，则 -
- 如果 val1 不等于 val2 且 (val1 + val2) 等于目标，则 -
- 打印配对 (val1 + val2 = 目标)
- 返回 true
- 否则，当 (val1 + val2) < 目标时，则 -
- done1 := false
- 否则，当 (val1 + val2) > 目标时，则 -
- done2 := false
- 如果 val1 >= val2，则 -
- 返回 false
- 当 done1 为 false 时，执行 -
示例
让我们看看以下实现以更好地理解 -
#include <bits/stdc++.h>
using namespace std;
#define MAX_SIZE 100
class TreeNode {
public:
int val;
TreeNode *left, *right;
TreeNode(int data) {
val = data;
left = NULL;
right = NULL;
}
};
bool isPairPresent(TreeNode* root, int target) {
stack<TreeNode*> s1, s2;
bool done1 = false, done2 = false;
int val1 = 0, val2 = 0;
TreeNode *curr1 = root, *curr2 = root;
while (true) {
while (done1 == false) {
if (curr1 != NULL) {
s1.push(curr1);
curr1 = curr1->left;
}
else {
if (s1.empty())
done1 = 1;
else {
curr1 = s1.top();
s1.pop();
val1 = curr1->val;
curr1 = curr1->right;
done1 = 1;
}
}
}
while (done2 == false) {
if (curr2 != NULL) {
s2.push(curr2);
curr2 = curr2->right;
}
else {
if (s2.empty())
done2 = 1;
else {
curr2 = s2.top();
s2.pop();
val2 = curr2->val;
curr2 = curr2->left;
done2 = 1;
}
}
}
if ((val1 != val2) && (val1 + val2) == target) {
cout << "Pair Found: " << val1 << " + " << val2 << " = " << target << endl;
return true;
}
else if ((val1 + val2) < target)
done1 = false;
else if ((val1 + val2) > target)
done2 = false;
if (val1 >= val2)
return false;
}
}
int main() {
TreeNode* root = new TreeNode(16);
root->left = new TreeNode(11);
root->right = new TreeNode(21);
root->left->left = new TreeNode(9);
root->left->right = new TreeNode(13);
root->right->left = new TreeNode(17);
root->right->right = new TreeNode(26);
int target = 35;
cout << (isPairPresent(root, target));
}输入
TreeNode* root = new TreeNode(16); root->left = new TreeNode(11); root->right = new TreeNode(21); root->left->left = new TreeNode(9); root->left->right = new TreeNode(13); root->right->left = new TreeNode(17); root->right->right = new TreeNode(26);
输出
Pair Found: 9 + 26 = 35 1
更新于: 2020-08-28
80 次查看
广告