在本文中，我將盡力解釋一些您在編碼面試之前應(yīng)該學(xué)習(xí)的核心算法。

什么是二叉搜索樹(shù) (BST)？

在編碼面試中很常見(jiàn)，BST 是一種樹(shù)狀數(shù)據(jù)結(jié)構(gòu)，頂部有一個(gè)根。它們是存儲(chǔ)數(shù)值的好方法，因?yàn)樗鼈兊挠行蛐再|(zhì)允許快速搜索和查找。

與普通樹(shù)相比，BST 具有以下特性：

• 每個(gè)左孩子的值都比它的父母小
• 每個(gè)右孩子的值都比它的父母大
• 每個(gè)節(jié)點(diǎn)可以包含 0 到 2 個(gè)子節(jié)點(diǎn)。

下圖應(yīng)該更清楚地說(shuō)明事情。

二叉樹(shù)節(jié)點(diǎn)的定義

我們通常在 Javascript 中定義一個(gè)二叉樹(shù)節(jié)點(diǎn)，函數(shù)如下：

 function TreeNode(val, left, right) {
     this.val = val
     this.left = left
     this.right = right
 }

二叉樹(shù)基本遍歷（中序、后序、前序）

首先要知道如何遍歷 BST 的每個(gè)節(jié)點(diǎn)。這允許我們?cè)?BST 的所有節(jié)點(diǎn)上執(zhí)行一個(gè)功能。例如，如果我們想x在 BST 中找到一個(gè)值，我們就需要節(jié)點(diǎn)。

有三種主要方法可以做到這一點(diǎn)。幸運(yùn)的是，他們有共同的主題。

中序遍歷

遞歸算法是開(kāi)始使用二叉樹(shù)中序遍歷的最簡(jiǎ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 算法從左、中、右遍歷樹(shù)節(jié)點(diǎn)。

const inorder = (root) => {
    const nodes = []
    if (root) {
        inorder(root.left)
        nodes.push(root.val)
        inorder(root.right)
    }
    return nodes
}
// 對(duì)于我們的示例樹(shù)，將返回 [1,2,3,4,5,6]

后序遍歷

遞歸算法是開(kāi)始后序遍歷的最簡(jiǎn)單方法。

• 如果節(jié)點(diǎn)為空，則什么都不做——否則，遞歸調(diào)用節(jié)點(diǎn)左子節(jié)點(diǎn)上的函數(shù)。
• 當(dāng)沒(méi)有更多的左孩子時(shí)，調(diào)用 node.right 上的函數(shù)。
• 最后，在節(jié)點(diǎn)上做一些操作。

后序遍歷從左、右、中訪問(wèn)樹(shù)節(jié)點(diǎn)。

const postorder = (root) => {
    const nodes = []
    if (root) {
        postorder(root.left)
        postorder(root.right)
        nodes.push(root.val)
    }
    return nodes
}
// 對(duì)于我們的示例樹(shù)，將返回 [1,3,2,6,5,4]

前序遍歷

遞歸算法是開(kāi)始前序遍歷的最簡(jiǎn)單方法。

• 如果節(jié)點(diǎn)為空，則什么都不做——否則，在節(jié)點(diǎn)上做一些操作。
• 遍歷節(jié)點(diǎn)的左子節(jié)點(diǎn)并重復(fù)。
• 遍歷到節(jié)點(diǎn)的右孩子并重復(fù)。

后序遍歷從中、左、右訪問(wèn)樹(shù)節(jié)點(diǎn)。

const preorder = (root) => {
    const nodes = []
    if (root) {
        nodes.push(root.val)
        preorder(root.left)
        preorder(root.right)
    }
    return nodes
}
// 對(duì)于我們的示例樹(shù)，將返回 [4,2,1,3,5,6]

什么是有效的二叉搜索樹(shù)？

有效的二叉搜索樹(shù) (BST) 具有所有值小于父節(jié)點(diǎn)的左子節(jié)點(diǎn)，以及值大于父節(jié)點(diǎn)的所有右子節(jié)點(diǎn)。
要驗(yàn)證一棵樹(shù)是否是有效的二叉搜索樹(shù)：

• 定義當(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)的值

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)
}

如何找到二叉樹(shù)最大深度

在這里，算法試圖找到我們 BST 的高度/深度。換句話(huà)說(shuō)，我們正在查看 BST 包含多少個(gè)“級(jí)別”。

• 如果節(jié)點(diǎn)為空，我們返回 0 因?yàn)樗鼪](méi)有添加任何深度
• 否則，我們將 + 1 添加到我們當(dāng)前的深度（我們遍歷了一層）
• 遞歸計(jì)算節(jié)點(diǎn)子節(jié)點(diǎn)的深度并返回node.left和node.right之間的最大和

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)
};

如何找到兩個(gè)樹(shù)節(jié)點(diǎn)之間的最小公共祖先

讓我們提高難度。我們?nèi)绾卧谖覀兊亩鏄?shù)中找到兩個(gè)樹(shù)節(jié)點(diǎn)之間的共同祖先？讓我們看一些例子。

在這棵樹(shù)中，3和1的最低共同祖先是2。3和2的LCA是2。6和1和6的LCA是4。

看到這里的模式了嗎？?jī)蓚€(gè)樹(shù)節(jié)點(diǎn)之間的 LCA 要么是節(jié)點(diǎn)本身之一（3 和 2 的情況），要么是父節(jié)點(diǎn)，其中第一個(gè)子節(jié)點(diǎn)位于其左子樹(shù)中的某處，而第二個(gè)子節(jié)點(diǎn)位于其右子樹(shù)中的某處。

尋找兩個(gè)樹(shù)節(jié)點(diǎn) p 和 q 之間的最低共同祖先（LCA）的算法如下：

• 驗(yàn)證是否在左子樹(shù)或右子樹(shù)中找到 p 或 q
• 然后，驗(yàn)證當(dāng)前節(jié)點(diǎn)是 p 還是 q
• 如果在左子樹(shù)或右子樹(shù)中找到 p 或 q 之一，并且 p 或 q 之一是節(jié)點(diǎn)本身，我們就找到了 LCA
• 如果在左子樹(shù)或右子樹(shù)中都找到了 p 和 q，我們就找到了 LCA

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
};

😊 結(jié)尾想說(shuō)的

到此，我們已經(jīng)學(xué)會(huì)了如何遍歷、驗(yàn)證和計(jì)算 BST 的深度。

到此這篇關(guān)于面向JavaScript入門(mén)初學(xué)者的二叉搜索樹(shù)算法教程的文章就介紹到這了,更多相關(guān)JavaScript二叉搜索樹(shù)算法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論