資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會研究
時尚研究
法律研究JavaScript 中 BST 中的兩數之和
問題
我們需要編寫一個 JavaScript 函式，該函式將兩個二叉查詢樹的根節點分別作為第一個和第二個引數接收。該函式的第三個引數是一個數字 target。
當且僅當第一個樹中有一個節點和第二個樹中有一個節點的值相加等於給定整數 target 時，我們的函式應返回 True，否則返回 false。
例如，如果輸入函式的引數是 −
const target = 23;
BST
則輸出應為 −
const output = true;
輸出說明
因為第一個樹中有 6，第二個樹中有 17，其和為 23。
示例
程式碼如下 −
class Node{
constructor(data) {
this.data = data;
this.left = null;
this.right = null;
};
};
class BinarySearchTree{
constructor(){
// root of a binary seach tree
this.root = null;
}
insert(data){
var newNode = new Node(data);
if(this.root === null){
this.root = newNode;
}else{
this.insertNode(this.root, newNode);
};
};
insertNode(node, newNode){
if(newNode.data < node.data){
if(node.left === null){
node.left = newNode;
}else{
this.insertNode(node.left, newNode);
};
} else {
if(node.right === null){
node.right = newNode;
}else{
this.insertNode(node.right,newNode);
};
};
};
};
const tree1 = new BinarySearchTree();
tree1.insert(1);
tree1.insert(3);
tree1.insert(4);
tree1.insert(2);
tree1.insert(4);
tree1.insert(5);
tree1.insert(6);
const tree2 = new BinarySearchTree();
tree2.insert(9);
tree2.insert(6);
tree2.insert(11);
tree2.insert(3);
tree2.insert(8);
tree2.insert(10);
tree2.insert(17);
const twoSumBSTs = (root1, root2, target) => {
if(root1 == null || root2 == null) return false;
if(root1.data + root2.data == target) return true;
if(root1.data + root2.data < target) {
return twoSumBSTs(root1.right, root2, target) || twoSumBSTs(root1, root2.right, target);
}else{
return twoSumBSTs(root1.left, root2, target) || twoSumBSTs(root1,
root2.left, target);
};
};
const target = 23;
console.log(twoSumBSTs(tree1.root, tree2.root, target));輸出
控制檯中的輸出將是 −
true
更新日期： 07-Apr-2021
123 檢視次數
廣告