算法:有序数组生成二叉搜索树
2022/2/27 12:51:23
本文主要是介绍算法:有序数组生成二叉搜索树,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
最近面试的时候遇到这个题目,但当时没有答出来,结束之后我恶补了一下,并在此记录一下加深印象。
二叉搜索树
二叉搜索树的每个节点总是大于它的左节点,小于它的右节点,这便是他的基本定义。因此相同数量的节点下它的高度是最低的,故而也是二叉树中查询效率最高的。而最重要的是:对二叉搜索树进行中序遍历即得到一个递增排序的序列。因为中序遍历之后根节点会在中间位置输出,这样一来我们便可知道二叉搜索树的根节点总是有序数组的中间元素。
有序数组转搜索树
既然中间元素便是树的根节点,我们就可以从中点开始使用分治法进行叶子结点的插入
// 首先定义二叉树节点 class TreeNode { val: number left: TreeNode | null = null right: TreeNode | null = null constructor(val: number) { this.val = val } } function sortedArrayToBST(arr: number[]) { return helper(arr, 0, arr.length - 1) } function helper(arr: number[], begin: number, end: number) { if (begin > end) return null // 根节点是中间元素(以此类推,每个分支的节点都是其子孙节点的中间元素) const mid = Math.ceil((begin + end) / 2) const n1 = new TreeNode(arr[mid]) // 从中间开始分开对根节点两边叶子结点进行数据插入 n1.left = helper(arr, begin, mid - 1) n1.right = helper(arr, mid + 1, end) return n1 }
测试运行
首先实现一个简单的中序遍历函数
function inorderTraversal(node: TreeNode) { if (node.left) inorderTraversal(node.left) console.log(node.val) if (node.right) inorderTraversal(node.right) }
然后测试1到10的有序数组插入
const arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] const n1 = sortedArrayToBST(arr) n1 && inorderTraversal(n1) // 输出:1 2 3 4 5 6 7 8 9 10
这篇关于算法:有序数组生成二叉搜索树的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)