【LeetCode每天一题】Convert Sorted Array to Binary Search Tree(根据有序数组构建平衡二叉树)

佚名 6年前 (2019-05-15) 随笔 1202人围观抢沙发百度已收录

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

Given the sorted array: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

      0
     / \
   -3   9
   /   /
 -10  5

思路

　　根据题目的意思我们需要根据有序数组来构建一个平衡二叉树，并且要满足平衡二叉树的定义。这个题我们可以使用分而治之的思想来解决。就是每次将数组分成两部分左边是左子树的部分，右边是右子树的部分。依次划分，知道数组划分完毕。代码的话最好使用递归来进行解决。
　　另外，leetcode上还有一道和这道类似的，只不过另外一道中是链表而不是数组。其实这道题我们可以先将链表中的数字存储到数组中，然后按照上面的办法来构建二叉树，单数如果不使用辅助空间的话，解决相对于数组就麻烦一些，每次都需要求链表的中间节点来进行不断的遍历。依次反复。
解决代码

 1 # Definition for a binary tree node.
 2 # class TreeNode(object):
 3 # def __init__(self, x):
 4 # self.val = x
 5 # self.left = None
 6 # self.right = None
 7 
 8 class Solution(object):  9     def sortedArrayToBST(self, nums): 10         """
11  :type nums: List[int] 12  :rtype: TreeNode 13         """
14         if not nums: # 数组为空直接返回None 15             return None 16         if len(nums) == 1: # 当数组中只有一个数据时返回构造的节点 17             return TreeNode(nums[0]) 18         mid = len(nums) // 2      #去数值的中间值
19         root = TreeNode(nums[mid]) # 根据中间值构造节点 20         root.left = self.sortedArrayToBST(nums[:mid]) # 左子树的节点 21         root.right = self.sortedArrayToBST(nums[mid+1:]) # 右子树的节点 22         return root  # 返回当前节点