資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究在 Java 中查詢平衡 BST 中具有給定和的配對
概念
針對給定的平衡二叉搜尋樹和目標和，我們編寫一個函式，如果存在和等於目標和的配對，則返回 true，否則返回 false。在這種情況下，期望的時間複雜度為 O(n)，並且只能實現 O(Logn) 的額外空間。在此，不允許對二叉搜尋樹進行任何修改。我們需要注意的是，平衡 BST 的高度始終為 O(Logn)。
示例
方法
根據蠻力解決方案，我們考慮 BST 中的每一對，並驗證其和是否等於 X。此解決方案的時間複雜度將為 O(n^2)。
現在，一個更好的解決方案是構建一個輔助陣列，並將 BST 的中序遍歷儲存在陣列中。在這種情況下，陣列將被排序，因為 BST 的中序遍歷始終生成排序資料。因此，在中序遍歷可用後，我們可以在 O(n) 時間內配對。請記住，此解決方案在 O(n) 時間內工作，但需要 O(n) 的輔助空間。
示例
// Java code to find a pair with given sum
// in a Balanced BST
import java.util.ArrayList;
// A binary tree node
class Node1 {
int data1;
Node1 left1, right1;
Node1(int d){
data1 = d;
left1 = right1 = null;
}
}
public class BinarySearchTree {
// Indicates root of BST
Node1 root1;
// Indicates constructor
BinarySearchTree(){
root1 = null;
}
// Indicates inorder traversal of the tree
void inorder(){
inorderUtil1(this.root1);
}
// Indicates utility function for inorder traversal of the tree
void inorderUtil1(Node1 node1){
if (node1 == null)
return;
inorderUtil1(node1.left1);
System.out.print(node1.data1 + " ");
inorderUtil1(node1.right1);
}
// Now this method mainly calls insertRec()
void insert(int key1){
root1 = insertRec1(root1, key1);
}
/* Indicates a recursive function to insert a new key in BST */
Node1 insertRec1(Node1 root1, int data1){
/* So if the tree is empty, return a new node */
if (root1 == null) {
root1 = new Node1(data1);
return root1;
}
/* Otherwise, recur down the tree */
if (data1 < root1.data1)
root1.left1 = insertRec1(root1.left1, data1);
else if (data1 > root1.data1)
root1.right1 = insertRec1(root1.right1, data1);
return root1;
}
// Indicates method that adds values of given BST into ArrayList
// and hence returns the ArrayList
ArrayList<Integer> treeToList(Node1 node1, ArrayList<Integer> list1){
// Indicates Base Case
if (node1 == null)
return list1;
treeToList(node1.left1, list1);
list1.add(node1.data1);
treeToList(node1.right1, list1);
return list1;
}
// Indicates method that checks if there is a pair present
boolean isPairPresent(Node1 node1, int target1){
// Now this list a1 is passed as an argument
// in treeToList method
// which is later on filled by the values of BST
ArrayList<Integer> a1 = new ArrayList<>();
// Now a2 list contains all the values of BST
// returned by treeToList method
ArrayList<Integer> a2 = treeToList(node1, a1);
int start1 = 0; // Indicates starting index of a2
int end1 = a2.size() - 1; // Indicates ending index of a2
while (start1 < end1) {
if (a2.get(start1) + a2.get(end1) == target1) // Target Found!{
System.out.println("Pair Found: " + a2.get(start1) + " + " + a2.get(end1) + " " + "= " + target1);
return true;
}
if (a2.get(start1) + a2.get(end1) > target1)
// decrements end
{
end1--;
}
if (a2.get(start1) + a2.get(end1) < target1)
// increments start
{
start1++;
}
}
System.out.println("No such values are found!");
return false;
}
// Driver function
public static void main(String[] args){
BinarySearchTree tree1 = new BinarySearchTree();
/*
16
/ \
11 21
/ \ / \
9 13 17 26 */
tree1.insert(16);
tree1.insert(11);
tree1.insert(21);
tree1.insert(9);
tree1.insert(13);
tree1.insert(17);
tree1.insert(26);
tree1.isPairPresent(tree1.root1, 34);
}
}輸出
Pair Found: 13 + 21 = 34
更新於： 2020-07-23
162 次檢視
廣告