LeetCode精选Top面试题之将有序数组转换为二叉搜索树-一一网

这是我参与更文挑战的第8天，活动详情查看：更文挑战

前言

公众号给npy的前端秘籍

加vx?16639199716,拉你进群嗷~❤️

今天继续学习LeetCode精选面试题，今天选择第108题进行学习与总结~

题目描述

给你一个整数数组 nums ，其中元素已经按升序排列，请你将其转换为一棵高度平衡二叉搜索树。

高度平衡二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

示例1

输入：nums = [-10,-3,0,5,9]

输出：[0,-3,9,-10,null,5]

解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案。

示例2

输入：nums = [1,3]

输出：[3,1]

解释：[1,3] 和 [3,1] 都是高度平衡二叉搜索树。

先来个饭甜品

二叉查找树：

二叉查找树就是左结点小于根节点，右结点大于根节点的一种排序树，也叫二叉搜索树。也叫BST，英文Binary Sort Tree。

二叉查找树比普通树查找更快，查找、插入、删除的时间复杂度为O（logN）。但是二叉查找树有一种极端的情况，就是会变成一种线性链表似的结构。此时时间复杂度就变味了O（N），为了解决这种情况，出现了二叉平衡树。

平衡二叉树：

平衡二叉树全称平衡二叉搜索树，也叫AVL树。是一种自平衡的树。

AVL树也规定了左结点小于根节点，右结点大于根节点。并且还规定了左子树和右子树的高度差不得超过1。这样保证了它不会成为线性的链表。AVL树的查找稳定，查找、插入、删除的时间复杂度都为O（logN），但是由于要维持自身的平衡，所以进行插入和删除结点操作的时候，需要对结点进行频繁的旋转。

解题思路：

题目要求构建高度平衡二叉搜索树，找到解决问题的突破口。

将有序数组一分为二，中间结点成为根结点，前半部分是左子树，右半部分是右子树；
递归构建左子树和右子树，应用到分治思想。

什么是分而治之呢？

分而治之是算法设计中的一种方法
它将一个问题分成多个和原问题相似的小问题,递归解决小问题,再将结果合并以解决原来的问题

构建一棵树包括：

构建 root、构建 root.left 和 root.right
题目要求“高度平衡”——构建 root 时，选数组的中间元素作为 root 节点值，即可保证平衡
递归函数的可以传数组，也可以传指针，前者每次都要切割数组，我选择指针：start、end，分别代表参与构建BST的数组的首尾索引。

const buildBST = (nums, start, end) => {
    if (start > end) { // 构成不了区间，返回null
      return null;
    }

    const midIndex = (start + end) >>> 1; // 求中间索引
    const root = new TreeNode(nums[midIndex]); // 构建当前节点

    root.left = buildBST(nums, start, midIndex - 1); // 构建左子树
    root.right = buildBST(nums, midIndex + 1, end); // 构建右子树

    return root;
};
var sortedArrayToBST = function(nums) {
    return buildBST(nums, 0, nums.length - 1); // 递归的入口
};
//时间复杂度：用O(1)的时间找到数组中间的元素，每个元素都被遍历到，所以是O(n)
//空间复杂度：递归占用的栈空间：O(logn）
复制代码