本文主要是介绍【LintCode 简单】177. 把排序数组转换为高度最小的二叉搜索树,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
1.问题描述:
给一个排序数组(从小到大),将其转换为一棵高度最小的排序二叉树。
注意事项
There may exist multiple valid solutions, return any of them.
2.样例:
给出数组 [1,2,3,4,5,6,7]
, 返回
4/ \2 6/ \ / \
1 3 5 7
3. 代码:
根据二叉搜索树的定义,本题首先需要找到一个排序数组的中间值mid作为二叉树的根结点
然后使用递归的方法,分别在左右子树上找到新的中间值
"""
Definition of TreeNode:
class TreeNode: def __init__(self, val):self.val = val self.left, self.right = None, None
""" class Solution:
"""
@param: A: an integer array
@return: A tree node
""" def sortedArrayToBST(self, A):# write your code here length=len(A) if length==0: return None else: mid=(length-1)/2 root=TreeNode(A[mid]) B=A[:mid] C=A[mid+1:] root.left=self.sortedArrayToBST(B) root.right=self.sortedArrayToBST(C) return root
这篇关于【LintCode 简单】177. 把排序数组转换为高度最小的二叉搜索树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!