本文面向 JavaScript 初学者，详解二叉搜索树 (BST) 的核心算法。内容涵盖 BST 定义、节点结构，深入解析中序、前序、后序三种递归遍历方法，以及验证 BST 有效性、计算最大深度和求解两个节点最低公共祖先 (LCA) 的具体实现逻辑与代码示例。
本文将重点介绍在准备编码面试时需要掌握的一些核心算法知识。
什么是二叉搜索树 (BST)？
二叉搜索树在编码面试中非常常见，它是一种树形数据结构，顶部包含一个根节点。由于其有序的特性，BST 非常适合存储数值数据，能够实现快速的搜索和查找操作。
与普通树相比，二叉搜索树具备以下关键特性：
- 每个左子节点的值必须小于其父节点的值。
- 每个右子节点的值必须大于其父节点的值。
- 每个节点可以包含 0 到 2 个子节点。
下图可以更直观地展示上述结构关系。
二叉树节点的定义
在 JavaScript 中，我们通常通过构造函数来定义二叉树节点，具体实现如下：
function TreeNode(val, left, right) {
this.val = val
this.left = left
this.right = right
}
二叉树基本遍历（中序、后序、前序）
掌握 BST 的节点遍历是基础，这使我们能够对树中的所有节点执行特定功能。例如，若要在 BST 中查找值 x，必须遍历相关节点。
实现遍历主要有三种方式，它们遵循相似的递归逻辑。
中序遍历
使用递归算法进行中序遍历是最简单的方法，其核心思路如下：
- 若节点为空，则不执行任何操作；否则，递归调用该节点左子节点的遍历函数。
- 在遍历完所有左子节点后，对当前节点执行操作。此时，当前节点保证是树中最左侧的节点。
- 最后，递归调用该节点右子节点的遍历函数。
中序遍历的顺序是：左、中、右，依次访问树节点。
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]
后序遍历
同样，递归算法是开始后序遍历的最简便方式。
- 若节点为空，则不执行任何操作；否则，递归调用该节点左子节点的遍历函数。
- 当没有更多左子节点时，递归调用该节点右子节点的遍历函数。
- 最后，对当前节点执行操作。
后序遍历的顺序是：左、右、中，依次访问树节点。
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]
前序遍历
递归算法是开始前序遍历的最简单方法。
- 若节点为空，则不执行任何操作；否则，先对当前节点执行操作。
- 接着遍历该节点的左子节点并重复上述过程。
- 最后遍历该节点的右子节点并重复上述过程。
前序遍历的顺序是：中、左、右，依次访问树节点。
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) 要求所有左子节点的值小于父节点，所有右子节点的值大于父节点。验证一棵树是否为有效 BST 的方法如下：
- 定义当前节点允许的最小值和最大值范围。
- 若节点的值不在该范围内，则返回 false。
- 递归验证节点的左子节点，将最大边界设置为当前节点的值。
- 递归验证节点的右子节点，将最小边界设置为当前节点的值。
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 包含多少个“层级”。
- 若节点为空，返回 0，因为空节点不增加深度。
- 否则，将当前深度加 1（表示已遍历一层）。
- 递归计算左右子节点的深度，并返回 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)
};
如何找到两个树节点之间的最小公共祖先
接下来提升难度：如何在二叉树中找到两个节点的最小公共祖先 (LCA)？让我们通过示例分析。
在示例树中，节点 3 和 1 的最低共同祖先是 2；节点 3 和 2 的 LCA 是 2；节点 6 和 1 的 LCA 是 4。
观察上述模式可知，两个树节点之间的 LCA 要么是节点本身（如 3 和 2 的情况），要么是父节点，其中一个子节点位于其左子树中，另一个子节点位于其右子树中。
寻找两个树节点 p 和 q 之间最低公共祖先 (LCA) 的算法逻辑如下：
- 首先验证 p 或 q 是否位于左子树或右子树中。
- 接着验证当前节点是否为 p 或 q 本身。
- 若在左子树或右子树中找到 p 或 q 之一，且 p 或 q 之一是当前节点本身，则找到 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
};
😊 结尾想说的
至此，我们已经掌握了 BST 的遍历、有效性验证以及深度计算方法。
本文关于面向 JavaScript 入门初学者的二叉搜索树算法教程到此结束，更多相关 JavaScript 二叉搜索树算法内容请搜索本站以前的文章或继续浏览下面的相关文章，希望大家以后多多支持本站！