您好,登錄后才能下訂單哦!
這篇文章主要介紹了如何使用JavaScript實(shí)現(xiàn)二叉搜索樹算法,具有一定借鑒價(jià)值,感興趣的朋友可以參考下,希望大家閱讀完這篇文章之后大有收獲,下面讓小編帶著大家一起了解一下。
在編碼面試中很常見,BST(Binary search tree) 是一種樹狀數(shù)據(jù)結(jié)構(gòu),頂部有一個(gè)根。它們是存儲(chǔ)數(shù)值的好方法,因?yàn)樗鼈兊挠行蛐再|(zhì)允許快速搜索和查找。
與普通樹相比,BST 具有以下特性:
每個(gè)左孩子的值都比其父母小
每個(gè)右孩子的值都比它的父母大
每個(gè)節(jié)點(diǎn)可以包含 0 到 2 個(gè)子節(jié)點(diǎn)。
下圖應(yīng)該更清楚地說明事情。
我們通常在 Javascript 中定義一個(gè)二叉樹節(jié)點(diǎn),函數(shù)如下:
function TreeNode(val, left, right) {
this.val = val
this.left = left
this.right = right
}
首先要知道如何遍歷 BST 的每個(gè)節(jié)點(diǎn)。這允許我們?cè)?BST 的所有節(jié)點(diǎn)上執(zhí)行一個(gè)功能。例如,如果我們想在 BST 中找到一個(gè)值,我們就需要節(jié)點(diǎn)。
有三種主要方法可以做到這一點(diǎn)。幸運(yùn)的是,他們有共同的主題。
遞歸算法是開始使用二叉樹中序遍歷的最簡單方法。思路如下:
如果節(jié)點(diǎn)為空,則什么都不做——否則,遞歸調(diào)用節(jié)點(diǎn)左子節(jié)點(diǎn)上的函數(shù)。
然后,遍歷完所有左子節(jié)點(diǎn)后,對(duì)節(jié)點(diǎn)進(jìn)行一些操作。我們當(dāng)前的節(jié)點(diǎn)保證是最左邊的節(jié)點(diǎn)。
最后,調(diào)用 node.right 上的函數(shù)。
Inorder 算法從左、中、右遍歷樹節(jié)點(diǎn)。
/**
* @param {TreeNode} root
*/
const inorder = (root) => {
const nodes = []
if (root) {
inorder(root.left)
nodes.push(root.val)
inorder(root.right)
}
return nodes
}
// for our example tree, this returns [1,2,3,4,5,6]
遞歸算法是開始后序遍歷的最簡單方法。
如果節(jié)點(diǎn)為空,則什么都不做——否則,遞歸調(diào)用節(jié)點(diǎn)左子節(jié)點(diǎn)上的函數(shù)。
當(dāng)沒有更多的左孩子時(shí),調(diào)用 node.right 上的函數(shù)。
最后,在節(jié)點(diǎn)上做一些操作。
后序遍歷從左、右、中訪問樹節(jié)點(diǎn)。
/**
* @param {TreeNode} root
*/
const postorder = (root) => {
const nodes = []
if (root) {
postorder(root.left)
postorder(root.right)
nodes.push(root.val)
}
return nodes
}
// for our example tree, this returns [1,3,2,6,5,4]
遞歸算法是開始前序遍歷的最簡單方法。
如果節(jié)點(diǎn)為空,則什么都不做——否則,在節(jié)點(diǎn)上做一些操作。
遍歷節(jié)點(diǎn)的左子節(jié)點(diǎn)并重復(fù)。
遍歷到節(jié)點(diǎn)的右孩子并重復(fù)。
后序遍歷從中、左、右訪問樹節(jié)點(diǎn)。
/**
* @param {TreeNode} root
*/
const preorder = (root) => {
const nodes = []
if (root) {
nodes.push(root.val)
preorder(root.left)
preorder(root.right)
}
return nodes
}
// for our example tree, this returns [4,2,1,3,5,6]
有效的二叉搜索樹 (BST) 具有所有值小于父節(jié)點(diǎn)的左子節(jié)點(diǎn),以及值大于父節(jié)點(diǎn)的所有右子節(jié)點(diǎn)。
要驗(yàn)證一棵樹是否是有效的二叉搜索樹:
定義當(dāng)前節(jié)點(diǎn)可以具有的最小值和最大值
如果節(jié)點(diǎn)的值不在這些范圍內(nèi),則返回 false
遞歸驗(yàn)證節(jié)點(diǎn)的左孩子,最大邊界設(shè)置為節(jié)點(diǎn)的值
遞歸驗(yàn)證節(jié)點(diǎn)的右孩子,最小邊界設(shè)置為節(jié)點(diǎn)的值
/**
* @param {TreeNode} root
*/
const isValidBST = (root) => {
const helper = (node, min, max) => {
if (!node) return true
if (node.val <= min || node.val >= max) return false
return helper(node.left, min, node.val) && helper(node.right, node.val, max)
}
return helper(root, Number.MIN_SAFE_INTEGER, Number.MAX_SAFE_INTEGER)
}
在這里,算法試圖找到我們 BST 的高度/深度。換句話說,我們正在查看 BST 包含多少個(gè)“級(jí)別”。
如果節(jié)點(diǎn)為空,我們返回 0 因?yàn)樗鼪]有添加任何深度
否則,我們將 + 1 添加到我們當(dāng)前的深度(我們遍歷了一層)
遞歸計(jì)算節(jié)點(diǎn)子節(jié)點(diǎn)的深度并返回node.left和node.right之間的最大和
/**
* @param {TreeNode} root
*/
const maxDepth = function(root) {
const calc = (node) => {
if (!node) return 0
return Math.max(1 + calc(node.left), 1 + calc(node.right))
}
return calc(root)
};
讓我們提高難度。我們?nèi)绾卧谖覀兊亩鏄渲姓业絻蓚€(gè)樹節(jié)點(diǎn)之間的共同祖先?讓我們看一些例子。
在這棵樹中,3和1的最低共同祖先是2。3和2的LCA是2。6和1和6的LCA是4。
看到這里的模式了嗎?兩個(gè)樹節(jié)點(diǎn)之間的 LCA 要么是節(jié)點(diǎn)本身之一(3 和 2 的情況),要么是父節(jié)點(diǎn),其中第一個(gè)子節(jié)點(diǎn)位于其左子樹中的某處,而第二個(gè)子節(jié)點(diǎn)位于其右子樹中的某處。
尋找兩個(gè)樹節(jié)點(diǎn) p 和 q 之間的最低共同祖先(LCA)的算法如下:
驗(yàn)證是否在左子樹或右子樹中找到 p 或 q
然后,驗(yàn)證當(dāng)前節(jié)點(diǎn)是 p 還是 q
如果在左子樹或右子樹中找到 p 或 q 之一,并且 p 或 q 之一是節(jié)點(diǎn)本身,我們就找到了 LCA
如果在左子樹或右子樹中都找到了 p 和 q,我們就找到了 LCA
/**
* @param {TreeNode} root
* @param {TreeNode} p
* @param {TreeNode} q
*/
const lowestCommonAncestor = function(root, p, q) {
let lca = null
const isCommonPath = (node) => {
if (!node) return false
var isLeft = isCommonPath(node.left)
var isRight = isCommonPath(node.right)
var isMid = node == p || node == q
if (isMid && isLeft || isMid && isRight || isLeft && isRight) {
lca = node
}
return isLeft || isRight || isMid
}
isCommonPath(root)
return lca
};
感謝你能夠認(rèn)真閱讀完這篇文章,希望小編分享的“如何使用JavaScript實(shí)現(xiàn)二叉搜索樹算法”這篇文章對(duì)大家有幫助,同時(shí)也希望大家多多支持億速云,關(guān)注億速云行業(yè)資訊頻道,更多相關(guān)知識(shí)等著你來學(xué)習(xí)!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請(qǐng)聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。