資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會學
時裝學
法學在 JavaScript 中的二叉搜尋樹中找出最小絕對差
我們要求編寫一個 JavaScript 函式，採用包含此類數值資料的 BST 的根，例如：
1 \ 3 / 2
該函式應返回樹中任意兩個節點之間的最小絕對差。
例如：
對於以上樹，輸出應該是：
const output = 1;
這是因為 |1 - 2| = |3 - 2| = 1
示例
程式碼如下：
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 BST = new BinarySearchTree();
BST.insert(1);
BST.insert(3);
BST.insert(2);
const getMinimumDifference = function(root) {
const nodes = [];
const dfs = (root) => {
if(root) {
dfs(root.left);
nodes.push(root.data);
dfs(root.right);
};
};
dfs(root);
let result = nodes[1] - nodes[0];
for(let i = 1; i < nodes.length - 1; i++) {
result = Math.min(result, nodes[i + 1] - nodes[i]);
};
return result;
};
console.log(getMinimumDifference(BST.root));輸出
控制檯中的輸出將是：
1
更新於：03-三月-2021
169 次瀏覽
廣告