牡丹江哈尔滨网站建设,恢复原来的网站,app网站开发费用,刚建设的网站如何推广1 中序遍历和搜索树原理
二叉搜索树按照中序遍历正好是一个递增序列。其比较规范的定义是#xff1a;
若它的左子树不为空#xff0c;则左子树上所有节点的值均小于它的根节点的值#xff1b;若它的右子树不为空#xff0c;则右子树所有节点的值均大于它的根节点的值
若它的左子树不为空则左子树上所有节点的值均小于它的根节点的值若它的右子树不为空则右子树所有节点的值均大于它的根节点的值它的左、右子树也分别为二叉搜索树比如下面的例子 这两棵树的中序遍历分别是[1, 2, 3, 4, 5, 6, 7, 8, 9]和[6, 7, 8, 9]都是二叉搜索树。
2 二叉搜索树中搜索特定值
力扣700题给定二叉搜索树BST的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在则返回 NULL。
比如target为3给定二叉搜索树 5/ \3 4/ \1 2应该返回如下子树 3 / \1 22.1 递归实现
使用递归来实现先来分析一下有哪些情况
如果根节点root null或者root.val target就直接返回根节点如果target root.val,说明比右子树的值小去根节点的左子树进行查找searchBST(root.left, target);如果target root.val,说明比左子树的值大去根节点的右子树进行查找searchBST(root.right, target)。
递归完整代码如下
// 递归法
function searchBST(root, target) {// 如果根节点为空或者root.val target直接返回rootif (root null || root.val target) {return root;}// 如果target root.val,进入根节点的左子树查找// 如果target root.val进入根节点的右子树查找return target root.val ? searchBST(root.left, target) : searchBST(root.right, target);
}2.2 迭代实现
迭代逻辑
如果根节点root null或者root.val target进入下面的判断 如果target root.val,说明比右子树的值小去根节点的左子树进行查找root root.left;如果target root.val,说明比左子树的值大去根节点的右子树进行查找root root.right
迭代完整代码如下
// 迭代法
function searchBST(root, target) {// 如果根节点为空或者target root.valwhile (root !null target ! root.val) {// 如果target root.val,进入根节点的左子树查找,root root.left// 如果target root.val进入根节点的右子树查找,root root.rightroot (target root.val ? root.left : root.right);}return root;
}
3 验证二叉搜索树
力扣98题给你一个二叉树的根节点 root 判断其是否是一个有效的二叉搜索树。有效二叉树定义如下
节点的左子树只包含 小于 当前节点的数。节点的右子树只包含 大于 当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。
分析根据题目以及中序遍历的特性可以知道二叉搜索树中序遍历得到的序列是一个升序序列要判断是否是一个有效二叉树只需要在中序遍历的时候一边遍历一边检查当前节点的值是否大于前一个遍历到的节点值即可。
3.1 递归实现
递归实现代码如下
function isValidBST(root) {let pre Number.MIN_SAFE_INTEGER;return validBST(root);function validBST(node) {if (node null) {return true;}// 如果左子树某个元素不满足要求就退出if (!validBST(node.left)) {return false;}// 如果当前节点值≤中序遍历前一个节点的值不能满足二叉搜索树条件if (node.val pre) {return false;}pre node.val;return validBST(node.right);}
}3.2 迭代实现
测试用例的最小节点有可能是javascript中的最小值因此初始化preVal -Infinity。
function isValidBST(root) {const nodeStack [];let preVal -Infinity;while (nodeStack.length 0 || root ! null) {while (root ! null) {nodeStack.push(root);// 先遍历左子树root root.left;}// 比较左子树中间根节点与前一个节点的值如果小与前一个节点值说明不是二叉搜索树root nodeStack.pop();if (root.val preVal) {return false;}preVal root.val;// 再遍历右子树root root.right;}return true;
}
