二叉树大家都知道,二叉搜索树满足以下特征:
节点的左子树只包含小于当前节点的数
节点的右子树只包含大于当前节点的数
所有左子树和右子树自身必须也是二叉搜索树
二叉搜索树也叫二叉排序树,中序遍历二叉搜索树的结果就是一次递增的遍历。
一、二叉搜索树的建立
相关题目:leetcode 108.将有序数组转换为二叉搜索树 [中等]
那么如何将一个有序数组转换为一颗二叉搜索树?
二叉搜索树的每一个分支的根节点都是他的中间值。根据这个特征,用二分法来将有序数组转换为一颗二叉搜索树。
const sortedArrayToBST = nums => {
// 边界条件
if (nums.length === 0) {
return null;
}
if (nums.length === 1) {
return new TreeNode(nums[0]);
}
// 向下取整得到中间值
let mid = Math.floor(nums.length / 2);
let root = new TreeNode(nums[mid]);
// 递归 二分法
root.left = sortedArrayToBST(nums.slice(0, mid));
root.right = sortedArrayToBST(nums.slice(mid + 1));
return root;
};
接下来我们验证下一棵树是否满足二叉搜索树。
二、验证二叉搜索树
相关题目:leetcode 98.验证二叉搜索树 [中等]
思路就是,中序遍历如果满足递增的就行。
用一个max作为验证值的变量,用中序遍历前面的值和后面的值作比较,一直递增则满足二叉搜索树。
const isValidBST = root => {
let isValidBSTFlag = true;
let max = -Number.MAX_VALUE;
const orderSearch = root => {
if (root) {
orderSearch(root.left);
if (root.val > max) {
max = root.val;
} else {
isValidBSTFlag = false;
}
orderSearch(root.right);
}
}
orderSearch(root);
return isValidBSTFlag;
};
上一个非递归解法。
非递归中序遍历的思路就是使用栈,将节点的左子树压入直到叶节点,然后操作完左子树跟根节点后再操作右子树。
循环反复,直到栈空。
const isValidBST = root => {
if(!root) return true;
let stack = [];
let isValidBSTFlag = true;
let max = -Number.MAX_VALUE;
while (1) {
while(root != null){
stack.push(root);
root = root.left;
}
if (stack.length === 0) break;
let node = stack.pop();
if (node.val > max) {
max = node.val;
} else {
isValidBSTFlag = false;
break;
}
root = node.right;
}
return isValidBSTFlag;
}
三、二叉搜索树的插入
相关题目:leetcode 701.二叉搜索树中的插入操作 [中等]
将值插入二叉搜索树,只要树在插入后仍保持为二叉搜索树即可。
思路:找到大于插入节点值的节点,将要插入的节点作为该节点的左子树。注意细节。
这里还是用中序遍历,中序遍历能很好地解决一种情况,就是要插入的节点值比树中的所有节点还大。
这种情况,找到树中最大值的节点,将插入的节点作为该节点的右节点。
没用递归,方便理解。
const insertIntoBST = (root, val) => {
let stack = [];
let r = root;
let node = null;
while (1) {
while(root != null) {
stack.push(root);
root = root.left;
}
if (stack.length === 0) break;
node = stack.pop();
// 找到大于插入节点值的节点
if (node.val > val) {
let newNode = new TreeNode(val);
newNode.left = node.left;
// 这里是细节
node.left = newNode;
break;
}
root = node.right;
}
// 要插入的节点值比树中的所有节点还大
if (val > node.val) {
node.right = new TreeNode(val);
}
return r;
};
四、二叉搜索树的恢复
相关题目:leetcode 99.恢复二叉搜索树 [困难]
要求:二叉搜索树中的两个节点被错误地交换。请在不改变其结构的情况下,恢复这棵树。
思路:利用中序遍历找到错误的两个节点s1,s2。交换这两个节点。
用一个数组保存遍历的值,如果前一个节点大于后一个节点,则s1肯定是前一个节点,后一个节点不一定是s2,继续遍历寻找找到s2。
const recoverTree = root => {
let res = [];
let s1 = s2 = null;
const orderSearch = root => {
if (root) {
orderSearch(root.left);
if (res.length !== 0) {
if (res[res.length - 1].val > root.val) {
// 第一个找到的才是s1
!s1 && (s1 = res[res.length - 1]);
// 若有第二次,第二次的才是s2
s2 = root;
}
}
res.push(root)
orderSearch(root.right);
}
}
orderSearch(root);
[s1.val, s2.val] = [s2.val, s1.val];
return root;
};
总结:
二叉搜索树跟排序相关,总是围绕着中序遍历进行操作。
递归代码简洁但是不好理解,非递归相对容易理解一些,两者效率差不太大,看场景使用。
今天的文章【javascript实现】几道题目带你学习二叉搜索树分享到此就结束了,感谢您的阅读。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/20193.html