这个题目居然是简单难度,吓了我一跳,本来一看到这个题目,我还一时半会儿没有想出来,后来想想这个题目可以作为模版题目,必须搞明白的题目,也就释然了。因为这个题目当中蕴含的思想非常经典,是一种典型的建立平衡二叉搜索树的方法,本题目的方法还可以推广到其他题目。可以多用于熟悉建立平衡二叉树。既然提到了平衡二叉树,那么其中一个很重要的性质就是,如果我们取到了平衡二叉树的中点,那么我们则可以将这中点作为我们的root,然后依次向下建立平衡二叉树。在中点之下,左右子树的nodes数量之差,最多不超过1,这样就满足了avl树的条件。
第二,我们如果有序数组是偶数,我们可以取中点之后,或者中点之前的那个node作为我们的root,有两种取法都可以,也都是满足答案的。在取中点的时候,我们也用到了地板除法,也就是只取我们除到的结果后的整数部分即可。
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def sortedArrayToBST(self, nums: List[int]) -> TreeNode: def help(left,right): if left>right: return None else: mid=(left+right)//2 #或者使用 mid=(left+right+1)//2 #在这里建立新的node,然后从这里开始利用分治的思想,向下递归 root=TreeNode(nums[mid]) root.left=help(left,mid-1) root.right=help(mid+1,right) return root #这里return才能够将我们新建立的root返回出来 return help(0,len(nums)-1)