本文主要是介绍(分治算法6) leecode 108 将有序数组转换成二叉搜索树,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目描述
给定一个单链表的头节点 head ,其中的元素 按升序排序 ,将其转换为平衡二叉搜索树。
求解
二叉搜索树指的是中序遍历是二叉搜索树。 如果想要让二叉搜索树保持平衡,这种构建树的方式也不是唯一的。
我们可以选择中间数字作为二叉搜索树的根节点,这样分给左右子树的数字个数相同或者只相差1,可以使得树保持平衡。如果数组长度是奇数,则根节点的选择是唯一的,如果数组的长度是偶数,则可以选择中间位置左边的数字作为根节点或者选择根节点位置右边的数字作为根节点。
确定了平衡二叉搜索树的根节点之后,其余数字分别位于平衡二叉树的左子树和右子树中,左子树和右子树分别也是平衡二叉搜索树,因此可以通过递归的方式创建平衡二叉树。
方法一:中序遍历,总是选择中间位置左边的数字作为根节点
选择中间位置左边的数字作为根节点,则根节点的下标为 mid = (left+ right)/2,此处的除法为整数除法。
这篇关于(分治算法6) leecode 108 将有序数组转换成二叉搜索树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!