Q108 Convert Sorted Array to Binary Search Tree

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
解题思路:

首先明白平衡二叉树的定义,注意要是每个结点必须满足。因为是将一个有序数组转化为一个平衡二叉树,因此,答案可能不唯一。

递归,将中间元素作为根节点,然后将数组分为左右两部分。左边数组用于递归创建左子树,右边数组用于递归创建右子树,直到数组为空。

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

class Solution:
    def sortedArrayToBST(self, num):
        if not num:   # 如果数组为空
            return None
        mid = len(num) // 2
        root = TreeNode(num[mid])
        root.left = self.sortedArrayToBST(num[:mid])     # 递归构建左子树
        root.right = self.sortedArrayToBST(num[mid+1:])  # 递归构建右子树
        return root

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏刘君君

JDK8的ArrayList源码学习笔记

2887
来自专栏武培轩的专栏

剑指Offer-求1+2+3+...+n

package Other; /** * 求1+2+3+...+n * 求1+2+3+...+n,要求不能使用乘除法、for、while、if、else、...

3174
来自专栏数据结构笔记

数据结构(六):树

ADT Tree{ ​ 数据对象: ​ D={1=<i<=n, n>=0, a(i)属于 ElemType类型} ​ 数据关系: ​...

972
来自专栏余林丰

有关ArrayList常用方法的源码解析

jdk1.7.0_79   我相信几乎所有的同学在大大小小的笔试、面试过程中都会被问及ArrayList与LinkedList之间的异同点。稍有准备的人这些问...

2297
来自专栏用户画像

6.3.2 B+树基本概念

2)非叶根(不是叶子的根结点)结点至少有两棵子树,其他每个分支结点至少有【m/2】(向下取整)棵子树。(B树是要求至少2棵子树)

992
来自专栏机器学习和数学

[算法与数据结构] 《算法导论》堆排序笔记

堆排序的实现是靠叫做“堆”的数据结构来实现的。所以学习堆排序,首先要了解什么是堆 堆 堆是一个数组,每个结点表示数组中的一个元素,堆可以看做是一个近似的完全二叉...

3139
来自专栏java系列博客

Iterator在ArrayList中的源码实现

1892
来自专栏好好学java的技术栈

“365算法每日学计划”:06打卡-单向循环链表

单向循环链表是单链表的另一种形式,其结构特点是链表中最后一个结点的指针不再是结束标记,而是指向整个链表的第一个结点,从而使单链表形成一个环。

691
来自专栏老马说编程

(43) 剖析TreeMap / 计算机程序的思维逻辑

40节介绍了HashMap,我们提到,HashMap有一个重要局限,键值对之间没有特定的顺序,我们还提到,Map接口有另一个重要的实现类TreeMap,在Tre...

2148
来自专栏书山有路勤为径

排序数组转换为二叉查找树

已知一个排序的数组,将该数组转换为一个高度平衡的二叉查找树。 平衡的定义: 二叉查找树中,任意节点的两颗子树高度差不超过1. LeetCode 108

903

扫码关注云+社区

领取腾讯云代金券