LeetCode108 将有序数组转换为二叉搜索树

  • 作者:zyh
  • 分类:LeetCode
  • 发表日期:2020-07-03 9:59:19
  • 阅读(246)
  • 评论(0)

本题的难度为简单,其实从题目也可以看出来,有序数组与二叉搜索树,这里就要简单讲一下二叉搜索树的性质了。

二叉搜索树又称二叉查找树(Binary Search Tree)

定义:

(1)如果左子树不为空,则左子树上所有节点的值均小于或等于其根节点的值;

(2)如果右子树不为空,则右子树上所有节点的值均大于或等于其根节点的值;

(3)左右子树也分别为二叉搜索树;

但是题目描述的要求是将这个数组转换为平衡二叉搜索树,平衡二叉搜索树就是在二叉搜索数的基础上又增加了一个条件,即如果这棵二叉搜索树既有左子树也有右子树,那么左右子树的高度差的绝对值不能超过1。高度可能有点难理解,高度就是这棵树的深度,也就是从这棵树的根节点开始往下数,每一层即为一个深度。

了解了二叉搜索树的性质和平衡二叉搜索树的性质后,再去做题就简单了。

首先要找出树的根节点,因为本题给定的数组是有序的,那么要在数组中找出根节点的这个数,即这个数的左边都小于这个数,右边都大于这个数,那这个条件肯定很好找,只要不是第一个数和最后一个数,一定都满足这个条件,但是不要忘了,本题要求是左右字数的高度差绝对值不能超过1,那么也就表明,数组中要找的这个根节点的这个数,左边的个数和右边的个数一定要相等或者差的绝对值为1。

那就很明显可以找到,就是这个数组的中位数,也就是找出这个数组中最中间的那个数,也就找到了树的根节点,此数左边的都为左子树,右边的都为右子树,在利用递归对左右子树进行划分。

代码如下:

LeetCode108 将有序链表转换为二叉搜索树

提交评论

您尚未登录 :-( ,登录之后方可评论 登录 or 注册

评论列表

暂无评论