脚本宝典收集整理的这篇文章主要介绍了面向JavaScript入门初学者的二叉搜索树算法教程,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
在本文中,我将尽力解释一些您在编码面试之前应该学习的核心算法。
在编码面试中很常见,BST 是一种树状数据结构,顶部有一个根。它们是存储数值的好方法,因为它们的有序性质允许快速搜索和查找。
与普通树相比,BST 具有以下特性:
下图应该更清楚地说明事情。
二叉树节点的定义
我们通常在 Javascript 中定义一个二叉树节点,函数如下:
function TreeNode(val, left, right) { this.val = val this.left = left this.right = right }
首先要知道如何遍历 BST 的每个节点。这允许我们在 BST 的所有节点上执行一个功能。例如,如果我们想x在 BST 中找到一个值,我们就需要节点。
Inorder 算法从左、中、右遍历树节点。
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) 具有所有值小于父节点的左子节点,以及值大于父节点的所有右子节点。
要验证一棵树是否是有效的二叉搜索树:
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 包含多少个“级别”。
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) };
让我们提高难度。我们如何在我们的二叉树中找到两个树节点之间的共同祖先?让我们看一些例子。
在这棵树中,3和1的最低共同祖先是2。3和2的LCA是2。6和1和6的LCA是4。
看到这里的模式了吗?两个树节点之间的 LCA 要么是节点本身之一(3 和 2 的情况),要么是父节点,其中第一个子节点位于其左子树中的某处,而第二个子节点位于其右子树中的某处。
寻找两个树节点 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二叉搜索树算法内容请搜索脚本宝典以前的文章或继续浏览下面的相关文章希望大家以后多多支持脚本宝典!
以上是脚本宝典为你收集整理的面向JavaScript入门初学者的二叉搜索树算法教程全部内容,希望文章能够帮你解决面向JavaScript入门初学者的二叉搜索树算法教程所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。