青岛手机网站制作,凤台县美丽乡村建设网站,台州千寻网站建设公司,中国建设网官方网站app力扣108提将有序数组转换为二叉搜索树
近一年都比较关注算法相关的知识#xff0c;也刷了不少题#xff0c;之前的文章中大多也是算法相关的文章#xff0c;但是感觉每次遇到树相关的题型都不能应对自如#xff0c;因此还是有必要在相关知识上下功夫#xff0c;因此有此次…力扣108提将有序数组转换为二叉搜索树
近一年都比较关注算法相关的知识也刷了不少题之前的文章中大多也是算法相关的文章但是感觉每次遇到树相关的题型都不能应对自如因此还是有必要在相关知识上下功夫因此有此次总结以下是所有树相关的文章
数据结构与算法–面试必问AVL树原理及实现
数据结构与算法–二叉树的深度问题
数据结构与算法–二叉堆最大堆最小堆实现及原理
数据结构与算法–二叉查找树转顺序排列双向链表
数据结构与算法-- 二叉树中和为某一值的路径
数据结构与算法-- 二叉树后续遍历序列校验
数据结构与算法-- 广度优先打印二叉树
数据结构与算法–解决问题的方法- 二叉树的的镜像
数据结构与算法–重建二叉树
数据结构与算法–二叉查找树实现原理
数据结构与算法–二叉树实现原理
数据结构与算法–B树原理及实现
数据结构与算法–数字在排序数组中出现次数
数据结构与算法–死磕二叉树
数据结构与算法–二叉树第k个大的节点
数据结构与算法–力扣108提将有序数组转换为二叉搜索树
原题
给你一个整数数组 nums 其中元素已经按 升序 排列请你将其转换为一棵 高度平衡 二叉搜索树。高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。如下图所示
解析
如上题意高度平衡二叉查找树并且高度差不超过1这正好符合AVL树的定义AVLAdelson-Velskii 和landis树是带有平衡条件的二叉查找树这个平衡条件必须容易实现并且保证树的深度必须是O(logN)。因此我们让一棵AVL树中每个节点的左子树和右子树的高度最多相差1空树高度定义-1如下图左边是AVL树右边不是AVL树。 对AVl树的构建实现以及原理在之前的文章 数据结构与算法–面试必问AVL树原理及实现 有做详细的分析 算法分析如下 关键点一 升序 排列 的数组关键点二AVL树左子树小于根右子树大于根高度差小于1根据如上两个关键信息要得到一颗AVL树我们需要根的左右子树节点一样或者相差1根据AVL树的特性左小右大那么我们选取数组第中间大的数据作为根节点因为是升序排序那么0~length/2 就是左子树length/2 1 ~ length就是右子树同样的道理对应左子树中也可以同样看成是一颗AVL树对于右子树同样看成hi一颗AVL树得出一个递归的构建过程
算法实现
/*** 有序数组转换为高度平衡二叉搜索树AVL树* author liaojiamin* Date:Created in 16:34 2022/2/21*/
public class SortArrayToAvlTree {public static void main(String[] args) {int[] arr new int[20];Random random new Random();for (int i 0; i 20; i) {if(i 0){arr[i] random.nextInt(30);}else {arr[i] random.nextInt(30) arr[i-1];}System.out.print(arr[i] ,);}System.out.println();BinaryNode avlTree sortArrayToAVL(arr);printTreeMiddle(avlTree);}/*** 中序遍历* */public static void printTreeMiddle(BinaryNode binaryNode){if(binaryNode null){return;}printTreeMiddle(binaryNode.getLeft());System.out.println(binaryNode.getElement());printTreeMiddle(binaryNode.getRight());}/*** 有序数组递归构建AVL树* */public static BinaryNode sortArrayToAVL(int[] arr){if(arr null || arr.length 0){return null;}if(arr.length 1){return new BinaryNode(arr[0], null, null);}BinaryNode leftNode sortArrayToAVL(Arrays.copyOfRange(arr, 0, (arr.length/2)));BinaryNode rightNode sortArrayToAVL(Arrays.copyOfRange(arr, (arr.length/2)1,arr.length));BinaryNode rootNode new BinaryNode(arr[arr.length/2], leftNode, rightNode);return rootNode;}
}上一篇数据结构与算法一篇帮助你吃下KMP算法
