怎么用JavaScript 實(shí)現(xiàn)二叉搜索樹算法

在本文中，我將盡力解釋一些您在編碼面試之前應(yīng)該學(xué)習(xí)的核心算法。如果您不熟悉二叉樹的概念，我建議您查看百度百科頁面。如果您完全掌握了這些基本算法，您將能夠更輕松地解決更復(fù)雜的問題。

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

在編碼面試中很常見，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)該更清楚地說明事情。

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

我們通常在 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ǎ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ǎn)單方法。

• 如果節(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ǎn)單方法。

• 如果節(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)
};

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

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

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

看到這里的模式了嗎？?jī)蓚€(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
};

總結(jié)

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

這些算法經(jīng)常在編碼面試中被問到。在練習(xí)更高級(jí)的 BST 應(yīng)用程序之前了解它們很重要，比如找到兩個(gè)節(jié)點(diǎn)的 LCA。