LeetCode 108. Convert Sorted Array to Binary Search Tree.jpg
LeetCode 108. Convert Sorted Array to Binary Search Tree
Description
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:
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
描述
给定一个数组，其中元素按升序排序，将其转换为高度平衡的BST。
对于这个问题，高度平衡的二叉树被定义为:二叉树中每个节点的两个子树的深度从不相差超过1。
例：
给定排序数组：[ - 10，-3,0,5,9]，
一个可能的答案是：[0，-3,9，-10，null，5]，它代表以下高度平衡的BST：
0
/ \
-3 9
/ /
-10 5
思路
- 二叉树的题目使用递归求解比较简单.
- 为了构造一棵平衡二叉树，我们每次都从给定数组的中间取值作为根节点，然后以当前值左边的所有值作为当前节点的左子树.
- 当前值右边的所有节点作为当前节点的右子树.
- 递归返回条件是已经取完了数组中的所有数，没有其它数可取，此时我们返回空节点.
# -*- coding: utf-8 -*-
# @Author: 何睿
# @Create Date: 2018-12-30 13:18:09
# @Last Modified by: 何睿
# @Last Modified time: 2018-12-30 13:30:43
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def sortedArrayToBST(self, nums):
"""
:type nums: List[int]
:rtype: TreeNode
"""
if not nums:
return None
return self.recursion(0, len(nums)-1, nums)
def recursion(self, left, right, nums):
# 递归结束条件，当left大于right时,返回空节点
if left > right:
return None
# 取中间值作为当前根节点
middle = left+((right-left) >> 1)
# 声明根节点
root = TreeNode(nums[middle])
# 生成左子树
leftree = self.recursion(left, middle-1, nums)
# 生成右子树
rightree = self.recursion(middle+1, right, nums)
root.left = leftree
root.right = rightree
# 返回根节点
return root
