資料結構
網路
關係資料庫管理系統
作業系統
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 次檢視
廣告