本文共 2244 字,大约阅读时间需要 7 分钟。
将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。
本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
给定有序数组: [-10,-3,0,5,9],
一个可能的答案是:[0,-3,9,-10,null,5],它可以表示下面这个高度平衡二叉搜索树:
0 / \ -3 9 / / -10 5
这道题是要将有序数组转为二叉搜索树,所谓二叉搜索树,是一种始终满足 左<根<右 的特性的二叉树,如果将二叉搜索树按中序遍历的话,得到的就是一个有序数组了。那么反过来,我们可以得知,根节点应该是有序数组的中间点,从中间点分开为左右两个有序数组,在分别找出其中间点作为原中间点的左右两个子节点。
数组nums是一个升序数组,所以根节点的位置一定是 m = len(nums)//2 nums中索引值小于m的树都位于根节点的左子树上,而另一半位于根节点的右子树上。 然后进行递归调用。
# Definition for a binary tree node.# class TreeNode(object):# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution(object): def sortedArrayToBST(self, nums): """ :type nums: List[int] :rtype: TreeNode """ if not nums: return None mid=len(nums)//2#找到中间节点 root=TreeNode(nums[mid])#当前节点为根节点 root.left=self.sortedArrayToBST(nums[:mid])#小于当前根节点的作为左子树 root.right=self.sortedArrayToBST(nums[mid+1:])#大于当前根节点的作为右子树 return root
以下是Java版本:
先复习下什么是二叉搜索树(引自Wikipedia):
二叉查找树(Binary Search Tree),也称有序二叉树(ordered binary tree),排序二叉树(sorted binary tree),是指一棵空树或者具有下列性质的:
再复习下什么是平衡二叉树(引自GeekforGeek):
An empty tree is height-balanced. A non-empty binary tree T is balanced if: 1) Left subtree of T is balanced 2) Right subtree of T is balanced 3) The difference between heights of left subtree and right subtree is not more than 1.
解决方法是选中点构造根节点,然后递归的构造左子树和右子树。
这道题是二分查找树的题目,要把一个有序数组转换成一颗二分查找树。其实从本质来看,如果把一个数组看成一棵树(也就是以中点为根,左右为左右子树,依次下去)数组就等价于一个二分查找树。所以如果要构造这棵树,那就是把中间元素转化为根,然后递归构造左右子树。所以我们还是用二叉树递归的方法来实现,以根作为返回值,每层递归函数取中间元素,作为当前根和赋上结点值,然后左右结点接上左右区间的递归函数返回值。时间复杂度还是一次树遍历O(n),总的空间复杂度是栈空间O(logn)加上结果的空间O(n),额外空间是O(logn),总体是O(n)。代码如下:
1. public TreeNode sortedArrayToBST(int[] num) { 2. if(num==null || num.length==0) 3. return null; 4. return helper(num,0,num.length-1); 5. } 6. private TreeNode helper(int[] num, int l, int r) 7. { 8. if(l>r) 9. return null; 10. int m = (l+r)/2; 11. TreeNode root = new TreeNode(num[m]); 12. root.left = helper(num,l,m-1); 13. root.right = helper(num,m+1,r); 14. return root; 15. }
转载地址:http://fpuvi.baihongyu.com/