在本文中，我將盡力解釋一些您在編碼面試之前應(yīng)該學(xué)習(xí)的核心算法。如果您不熟悉二叉樹的概念，我建議您查看百度百科頁面。如果您完全掌握了這些基本算法，您將能夠更輕松地解決更復(fù)雜的問題。
什么是二叉搜索樹 (BST)？
在編碼面試中很常見，BST（Binary search tree） 是一種樹狀數(shù)據(jù)結(jié)構(gòu)，頂部有一個根。它們是存儲數(shù)值的好方法，因為它們的有序性質(zhì)允許快速搜索和查找。
與普通樹相比，BST 具有以下特性：
- 每個左孩子的值都比其父母小
- 每個右孩子的值都比它的父母大
- 每個節(jié)點可以包含 0 到 2 個子節(jié)點。
下圖應(yīng)該更清楚地說明事情。
二叉樹節(jié)點的定義
我們通常在 Javascript 中定義一個二叉樹節(jié)點，函數(shù)如下：
function TreeNode(val, left, right) {
this.val = val
this.left = left
this.right = right
}
二叉樹基本遍歷（中序、后序、前序）
首先要知道如何遍歷 BST 的每個節(jié)點。這允許我們在 BST 的所有節(jié)點上執(zhí)行一個功能。例如，如果我們想在 BST 中找到一個值，我們就需要節(jié)點。
有三種主要方法可以做到這一點。幸運的是，他們有共同的主題。
中序遍歷
遞歸算法是開始使用二叉樹中序遍歷的最簡單方法。思路如下：
- 如果節(jié)點為空，則什么都不做——否則，遞歸調(diào)用節(jié)點左子節(jié)點上的函數(shù)。
- 然后，遍歷完所有左子節(jié)點后，對節(jié)點進行一些操作。我們當(dāng)前的節(jié)點保證是最左邊的節(jié)點。
- 最后，調(diào)用 node.right 上的函數(shù)。
Inorder 算法從左、中、右遍歷樹節(jié)點。
/**
* @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ào)用節(jié)點左子節(jié)點上的函數(shù)。
- 當(dāng)沒有更多的左孩子時，調(diào)用 node.right 上的函數(shù)。
- 最后，在節(jié)點上做一些操作。
后序遍歷從左、右、中訪問樹節(jié)點。
/**
* @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é)點為空，則什么都不做——否則，在節(jié)點上做一些操作。
- 遍歷節(jié)點的左子節(jié)點并重復(fù)。
- 遍歷到節(jié)點的右孩子并重復(fù)。
后序遍歷從中、左、右訪問樹節(jié)點。
/**
* @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é)點的左子節(jié)點，以及值大于父節(jié)點的所有右子節(jié)點。
要驗證一棵樹是否是有效的二叉搜索樹：
- 定義當(dāng)前節(jié)點可以具有的最小值和最大值
- 如果節(jié)點的值不在這些范圍內(nèi)，則返回 false
- 遞歸驗證節(jié)點的左孩子，最大邊界設(shè)置為節(jié)點的值
- 遞歸驗證節(jié)點的右孩子，最小邊界設(shè)置為節(jié)點的值
/**
* @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 包含多少個“級別”。
- 如果節(jié)點為空，我們返回 0 因為它沒有添加任何深度
- 否則，我們將 + 1 添加到我們當(dāng)前的深度（我們遍歷了一層）
- 遞歸計算節(jié)點子節(jié)點的深度并返回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)
};
如何找到兩個樹節(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
- 然后，驗證當(dāng)前節(jié)點是 p 還是 q
- 如果在左子樹或右子樹中找到 p 或 q 之一，并且 p 或 q 之一是節(jié)點本身，我們就找到了 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é)會了如何遍歷、驗證和計算 BST 的深度。
這些算法經(jīng)常在編碼面試中被問到。在練習(xí)更高級的 BST 應(yīng)用程序之前了解它們很重要，比如找到兩個節(jié)點的 LCA。
