专栏首页编程拯救世界图解精选 TOP 面试题 004 | LeetCode 108. 将有序数组转换为二叉搜索树

图解精选 TOP 面试题 004 | LeetCode 108. 将有序数组转换为二叉搜索树

该系列题目取自 LeetCode 精选 TOP 面试题列表:https://leetcode-cn.com/problemset/top/

题目描述

原题链接:https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/

将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。

本题中,一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。

示例:

给定有序数组: [-10,-3,0,5,9],

一个可能的答案是:[0,-3,9,-10,null,5],它可以表示下面这个高度平衡二叉搜索树:

      0
     / \
   -3   9
   /   /
 -10  5

解题思路

题目给出了一个升序排序的有序数组,要求我们转换为一棵高度平衡二叉搜索树

在此之前,我们先来回忆一下什么是二叉搜索树。

二叉搜索树

二叉搜索树[1](Binary Search Tree)是指一棵空树或具有如下性质的二叉树:

  1. 若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值
  2. 若任意节点的右子树不空,则右子树上所有节点的值均大于它的根节点的值
  3. 任意节点的左、右子树也分别为二叉搜索树
  4. 没有键值相等的节点

基于以上性质,我们可以得出一个二叉搜索树的特性:二叉搜索树的中序遍历结果为递增序列

那么现在题目给了我们一个递增序列,要求我们构造一棵二叉搜索树,就是要我们实现这一特性的逆过程

还记得什么是中序遍历吗?中序遍历的顺序为:左节点 根节点 右节点。这个遍历过程可以使用递归非常直观地进行表示。

如何构造树

构造一棵树的过程可以拆分成无数个这样的子问题:构造树的每个节点以及节点之间的关系。对于每个节点来说,都需要:

  1. 选取节点
  2. 构造该节点的左子树
  3. 构造该节点的右子树

因题目要求构造一棵「高度平衡」的树,所以我们在选取节点时选择数组的中点作为根节点,以此来保证平衡性。

以题目给出的 [-10,-3,0,5,9] 为例。

我们选取数组中点,即数字 0 作为根节点。此时,以 0 为分界点将数组分为左右两个部分,左侧为 [-10, -3],右侧为 [5, 9]。因该数组为升序排列的有序数组,所以左侧数组值均小于 0,可作为节点 0 的左子树;右侧数组值均大于 0,可作为节点 0 的右子树。

同上述步骤,将 [-10, -3][5, 9] 单独看作两棵树,从而继续为他们构造左右子树。

对于左侧数组 [-10, -3],我们选取 -3 作为根节点;对于右侧数组 [5, 9],选取 9 作为根节点。

最终构造结果如下:

递归设计

函数作用

通过上述解题过程我们可以明确该问题的子问题是:构造树的每个节点以及该节点的左右子树。因此,递归函数的作用很明显:

  1. 选取要构造关系的节点并创建它
  2. 构造该节点的左子树
  3. 构造该节点的右子树

函数的输入为递增数组,函数的返回为完成构造的节点

何时结束

当输入的递增数组为空时,只能构成一棵空树,此时返回空节点。

何时调用

当构造节点的左右子树时,对递增数组进行拆分并进行递归调用。

具体实现

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, nums: List[int]) -> TreeNode:
        if not nums:
            return None

        # 找到中点作为根节点
        mid = len(nums) // 2
        node = TreeNode(nums[mid])

        # 左侧数组作为左子树
        left = nums[:mid]
        right = nums[mid+1:]

        # 递归调用
        node.left = self.sortedArrayToBST(left)
        node.right = self.sortedArrayToBST(right)

        return node

Go

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sortedArrayToBST(nums []int) *TreeNode {
    if len(nums) == 0 {
        return nil
    }

    mid := len(nums) / 2

    left := nums[:mid]
    right := nums[mid+1:]

    node := &TreeNode{nums[mid], sortedArrayToBST(left), sortedArrayToBST(right)}

    return node
}

复杂度

  • 时间复杂度:
  • 空间复杂度:

总结

  • 本题考察点:二叉搜索树、树的构造、中序遍历
  • 二叉搜索树左子树上所有节点的值均小于它的根节点的值,右子树上所有节点的值均大于它的根节点的值
  • 二叉搜索树的中序遍历结果为递增序列

参考资料

[1]

二叉搜索树: https://zh.wikipedia.org/wiki/%E4%BA%8C%E5%85%83%E6%90%9C%E5%B0%8B%E6%A8%B9

本文分享自微信公众号 - 编程拯救世界(CodeWarrior_),作者:江子抑

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-12-12

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 精选 TOP 面试题 001 | LeetCode 237. 删除链表中的节点

    请编写一个函数,使其可以删除某个链表中给定的(非末尾)节点,你将只被给定要求被删除的节点。

    江不知
  • 图解精选 TOP 面试题 005.1 | 反转链表之递归求解

    在上一篇《图解精选 TOP 面试题 005 | 反转链表之迭代求解》中,我们介绍了该题的迭代求解法,本篇再说说如何进行递归求解。

    江不知
  • 图解精选 TOP 面试题 002 | LeetCode 104. 二叉树的最大深度

    题目要求求出二叉树的最大深度,我们知道,每个节点的深度与它左右子树的深度有关,且等于其左右子树最大深度值加上 1,可以写作:

    江不知
  • 【深入学习MySQL】MySQL的索引结构为什么使用B+树?

    在MySQL中,无论是Innodb还是MyIsam,都使用了B+树作索引结构(这里不考虑hash等其他索引)。本文将从最普通的二叉查找树开始,逐步说明各种树解决...

    Java_老男孩
  • 游戏AI设计经验分享——行为树研究

    http://bbs.gameres.com/thread_493700.html

    李海彬
  • 整理得吐血了,二叉树、红黑树、B&B+树超齐全,快速搞定数据结构

    没有必要过度关注本文中二叉树的增删改导致的结构改变,规则操作什么的了解一下就好,看不下去就跳过,本文过多的XX树操作图片纯粹是为了作为规则记录,该文章主要目的是...

    Java程序猿阿谷
  • 后端开发之Redis必会概念

    RDB持久化是指将当前进程中的数据生成快照的方式保存到硬盘中。保存的文件名后缀时rdb。Redis重新启动的时候会读取快照中的文件进行恢复数据;

    陌无崖
  • 【GCN】图卷积网络入门(一)

    图是一种数据结构,可对一组对象(节点)及其关系(边)进行建模。近年来,由于图的强大表达能力,利用机器学习来分析图的研究受到越来越多的关注,即图可以用作包括社会科...

    yuquanle
  • 离散存储【链表】

        1、n个节点离散分布     2、彼此通过指针相连     3、每个节点只有一个前驱节点,每个节点只有一个后续节点     4、首节点没有前驱节点...

    Sky_Mao
  • Redis6.0主从、哨兵、集群搭建和原理

    由于单机Redis存储能力受单机限制,以及无法实现读写操作的负载均衡和读写分离,无法保证高可用。本篇就来介绍 Redis 集群搭建方案及实现原理,实现Redis...

    王知无

扫码关注云+社区

领取腾讯云代金券