python实现leetcode之108. 将有序数组转换为二叉

解题思路

使用标准的二分查找，确定中间元素作为root节点的值
然后左边的就是左子树，右边的就是右子树
递归处理左右两边即可

108. 将有序数组转换为二叉搜索树

代码

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def sortedArrayToBST(self, nums):
        """
        :type nums: List[int]
        :rtype: TreeNode
        """
        return array2tree(nums, 0, len(nums)-1)


def array2tree(arr, start, end):
    if start > end: return None
    mid = (start+end) / 2
    root = TreeNode(arr[mid])
    root.left = array2tree(arr, start, mid-1)
    root.right = array2tree(arr, mid+1, end)
    return root