题目：

给一个排序数组（从小到大），将其转换为一棵高度最小的排序二叉树。

样例

给出数组 [1,2,3,4,5,6,7], 返回

4   /   \  2     6 / \    / \1   3  5   7

挑战

可能有多个答案，返回任意一个即可

解题：

可以看出，这里的数组是所求二叉树，中序遍历的结果，把这个结果还原成树即可。曾经天勤数据结果好像有这一题。

Java程序：

/** * Definition of TreeNode: * public class TreeNode { *     public int val; *     public TreeNode left, right; *     public TreeNode(int val) { *         this.val = val; *         this.left = this.right = null; *     } * } */ public class Solution {    /**     * @param nums: an integer array     * @return: a tree node     */    public TreeNode sortedArrayToBST(int[] nums) {          // write your code here        if(nums==null)            return null;        return buildTree(nums,0,nums.length - 1);    }    public TreeNode buildTree(int[] nums,int start,int end){        if(start>end)            return null;        int median = (start+end)/2;        TreeNode node = new TreeNode(nums[median]);        node.left = buildTree(nums,start,median-1);        node.right = buildTree(nums,median+1,end);            return node;    }}

总耗时: 2855 ms

Python程序：

"""Definition of TreeNode:class TreeNode:    def __init__(self, val):        self.val = val        self.left, self.right = None, None"""class Solution:    """    @param nums: a list of integer    @return: a tree node    """    def sortedArrayToBST(self, nums):        # write your code here        if nums==None:            return None        return self.buildTree(nums,0,len(nums)-1)        def buildTree(self,nums,start,end):        if start>end:            return None        median = (start+end)//2        node = TreeNode(nums[median])        node.left = self.buildTree(nums,start,median-1)        node.right = self.buildTree(nums,median+1,end)        return node

总耗时: 869 ms