題目：

把排序數組轉換為高度最小的二叉搜索樹

給一個排序數組（從小到大），將其轉換為一棵高度最小的排序二叉樹。

樣例

給出數組?[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 hereif(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;} } View Code

總耗時:?2855?ms

Python程序：

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

總耗時:?869?ms

總結

以上是生活随笔為你收集整理的lintcode: 把排序数组转换为高度最小的二叉搜索树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。