在本文中，我將盡力解釋一些您在編碼面試之前應該學習的核心算法。

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

在編碼面試中很常見，BST 是一種樹狀數(shù)據(jù)結(jié)構(gòu)，頂部有一個根。它們是存儲數(shù)值的好方法，因為它們的有序性質(zhì)允許快速搜索和查找。

與普通樹相比，BST 具有以下特性：

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

下圖應該更清楚地說明事情。

二叉樹節(jié)點的定義

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

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

二叉樹基本遍歷（中序、后序、前序）

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

有三種主要方法可以做到這一點。幸運的是，他們有共同的主題。

中序遍歷

遞歸算法是開始使用二叉樹中序遍歷的最簡單方法。思路如下：

• 如果節(jié)點為空，則什么都不做——否則，遞歸調(diào)用節(jié)點左子節(jié)點上的函數(shù)。
• 然后，遍歷完所有左子節(jié)點后，對節(jié)點進行一些操作。我們當前的節(jié)點保證是最左邊的節(jié)點。
• 最后，調(diào)用 node.right 上的函數(shù)。

Inorder 算法從左、中、右遍歷樹節(jié)點。

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

后序遍歷

遞歸算法是開始后序遍歷的最簡單方法。

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

后序遍歷從左、右、中訪問樹節(jié)點。

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

前序遍歷

遞歸算法是開始前序遍歷的最簡單方法。

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

后序遍歷從中、左、右訪問樹節(jié)點。

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

什么是有效的二叉搜索樹？

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

• 定義當前節(jié)點可以具有的最小值和最大值
• 如果節(jié)點的值不在這些范圍內(nèi)，則返回 false
• 遞歸驗證節(jié)點的左孩子，最大邊界設置為節(jié)點的值
• 遞歸驗證節(jié)點的右孩子，最小邊界設置為節(jié)點的值

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 包含多少個“級別”。

• 如果節(jié)點為空，我們返回 0 因為它沒有添加任何深度
• 否則，我們將 + 1 添加到我們當前的深度（我們遍歷了一層）
• 遞歸計算節(jié)點子節(jié)點的深度并返回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)
};

如何找到兩個樹節(jié)點之間的最小公共祖先

讓我們提高難度。我們?nèi)绾卧谖覀兊亩鏄渲姓业絻蓚€樹節(jié)點之間的共同祖先？讓我們看一些例子。

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

看到這里的模式了嗎？兩個樹節(jié)點之間的 LCA 要么是節(jié)點本身之一（3 和 2 的情況），要么是父節(jié)點，其中第一個子節(jié)點位于其左子樹中的某處，而第二個子節(jié)點位于其右子樹中的某處。

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

• 驗證是否在左子樹或右子樹中找到 p 或 q
• 然后，驗證當前節(jié)點是 p 還是 q
• 如果在左子樹或右子樹中找到 p 或 q 之一，并且 p 或 q 之一是節(jié)點本身，我們就找到了 LCA
• 如果在左子樹或右子樹中都找到了 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é)尾想說的

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

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

最新評論