【javascript实现】几道题目带你学习二叉搜索树
栏目: JavaScript · 发布时间: 5年前
内容简介:那么如何将一个有序数组转换为一颗二叉搜索树?二叉搜索树的每一个分支的根节点都是他的中间值。根据这个特征,用二分法来将有序数组转换为一颗二叉搜索树。
相关题目: 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实现】几道题目带你学习二叉搜索树》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- 面试题目:反转链表的算法实现
- CSS题目系列(2) - 实现一个固定比例盒子
- 剑指Offer题目2:实现 Singleton 模式(Java)
- 一篇文章搞定面试中的链表题目(java实现)
- Java 基础系列 22:有关链表的经典面试题目解析与代码实现
- 数据结构和算法必知必会的 50 道题目 12 种语言代码实现
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。