【leetcode】108:将有序数组转化为二叉搜索树

这个题目居然是简单难度,吓了我一跳,本来一看到这个题目,我还一时半会儿没有想出来,后来想想这个题目可以作为模版题目,必须搞明白的题目,也就释然了。因为这个题目当中蕴含的思想非常经典,是一种典型的建立平衡二叉搜索树的方法,本题目的方法还可以推广到其他题目。可以多用于熟悉建立平衡二叉树。既然提到了平衡二叉树,那么其中一个很重要的性质就是,如果我们取到了平衡二叉树的中点,那么我们则可以将这中点作为我们的root,然后依次向下建立平衡二叉树。在中点之下,左右子树的nodes数量之差,最多不超过1,这样就满足了avl树的条件。

第二,我们如果有序数组是偶数,我们可以取中点之后,或者中点之前的那个node作为我们的root,有两种取法都可以,也都是满足答案的。在取中点的时候,我们也用到了地板除法,也就是只取我们除到的结果后的整数部分即可。

【leetcode】108:将有序数组转化为二叉搜索树

 

 

# 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)

 

上一篇:将有序数组转换为二叉搜索树-二叉树108-python


下一篇:[LeetCode] #108 将有序数组转换为二叉搜索树