Cần viết hàm JS nhận gốc của một BST chứa dữ liệu số. Hàm trả về độ chênh lệch tuyệt đối nhỏ nhất giữa hai nút bất kỳ của cây.
Ví dụ:
Với cây:
1 \ 3 / 2
Kết quả:
const output = 1;
vì |1-2| = |3-2| = 1
Ví dụ
Mã thực hiện:
class Node{ constructor(data) { this.data = data; this.left = null; this.right = null; }; }; class BinarySearchTree{ constructor(){ 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));
Kết quả
Kết quả in ra console:
1