有序数组转为二叉搜索树

高度平衡:二叉树是一棵满足每个节点的左右两个子树的高度差的绝对值不超过1的二叉树。

二叉搜索树的中序遍历就是有序数组相当于现在知道中序遍历的结果让你构造二叉树是不是很简单答案也有很多种但是这里限制了左右子树的高度差绝对值不能超过1答案就少了。

分析二叉搜索树的根节点的左子树上的结点的值都比根节点的值小根节点的右子树上的结点的值都比根节点的值大而根节点的左子树中的根节点也符合这一条件根节点的右子树中的根节点也符合这一条件。

mid

2;将数组用中间元素分出左右数组中间元素作为根节点再从左右数组中分别找出左右数组中的中间元素当作根节点的左右结点如此循环往复知道数组为空。

所以这本质上就是一个二分查找。

终止条件left

nullptr;}//总是选择中间位置左边的数字为根节点int

mid

TreeNode(nums[mid]);//返回mid左边数组构造的左子树root-left

helper(nums,

k位置上的数同时遍历两个数组比较大小移动指针找到第k个大的元素。

接下来使用二分的方法讲解当mn为奇数中位数是有序数组的第mn)/2个元素为偶数中位数是第(mn)/2个元素和第(mn)/2

假如有两个有序数组nums1和nums2要找到第k个元素我们先比较nums1[k/2-1]和nums2[k/2-1]。

比较完大小后有以下几种情况

如果nums1[k/2-1]

nums2[k/2-1],则比nums1[k/2-1]小的数最多只有nums1的前k/2

1]不可能是第k个数那么便可以排除掉nums1[0]到nums1[k/2

如下图中第一种情况

nums2[k/2-1],便可以排除掉nums2[0]到nums2[k/2

如下图中第二种情况

所以我们每次都能缩小一半范围那最后我们就可以以log的时间复杂度找到我们要的中位数啦

如果nums1[k/2

1]越界那我们我们可以选取其对应数组的最后一个元素。

在这种情况下我们必须根据排除的个数减少k的值而不能直接将k减去k/2。

int

findMedianSortedArrays(vectorint

nums1,