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