将排序的数组转换为二进制搜索树Leetcode解决方案  


难度级别 易得奖学金
经常问 土砖 Airbnb的 亚马逊 Apple 彭博 思科 谷歌 微软 神谕 Spotify VMware的 雅虎
算法 二进制搜索树 编码 深度优先搜索 访谈 面试准备 力码 力码解决方案

考虑给我们一个排序 排列 整数目标是从此数组构建二进制搜索树,以使树是高度平衡的。 请注意,如果树中任何节点的左右子树的高度差最大为1,则称该树为高度平衡。

不难发现可以有多种解决方案。 我们需要找到任何有效的解决方案。 请注意,在这个问题中,我们不需要打印树,而是创建一棵树。 我们只需要打印其遍历遍历。

使用案列  

Array = {-4 , 0 , 1 , 2 , 7}
1 -4 0 2 7

说明:BST是:

将排序的数组转换为二进制搜索树Leetcode解决方案

 

Array = {1 , 2 , 3}
2 1 3

说明:BST是:

将排序的数组转换为二进制搜索树Leetcode解决方案

方法(递归 

我们需要跟踪两件事:

  1. 任何节点都应具有较小的元素作为左子元素,反之亦然。
  2. BST应该保持高度平衡

为了随时保持树的平衡,我们必须选择数组的中间元素作为根。 这样,我们的高度差为 1 如果数组的大小均匀且高度差为,则在左右子树之间 当数组的大小为奇数时。

参见
四个Leetcode解决方案的力量

现在,当我们选择任何中间节点作为根节点时,我们必须从左子数组创建左子树,并从右子数组创建右子树。 这是我们原始问题的一个子问题,因此我们可以递归地解决它。 将左右子树分配给中间节点后,我们可以将其返回并打印二进制搜索树的后序遍历。

算法  

  1. 创建另一个功能 converArrayToBST() 它将转换给定数组的任何特定范围并返回其对应的BST根节点。
  2. 在上述范围内,令L =阵列的左极限,R =阵列的右极限。
    1. 如果L> R
      • 回报 ,因为我们收到错误的范围
    2. 如果L == R
      • 返回一个新节点,其值与 数组[L] 
    3. 找到该范围的中间节点为 中=(L +(R – L)/ 2)
      • 将head初始化为一个新BST节点,其值与 数组[中]
      • 分配 以及 子树的功能相同,分别在左侧和右侧子范围上调用
      • 回头
  3. 打印二分查找树的遍历遍历

将排序数组转换为二叉搜索树Leetcode解决方案的实现  

将排序后的数组转换为二进制搜索树的C ++解决方案

#include <bits/stdc++.h>
using namespace std;

struct BSTNode
{
    int value;
    BSTNode *left , *right;
    BSTNode(int x)
    {
        value = x;
        left = NULL;
        right = NULL;
    }
};

BSTNode* convertArrayToBST(vector <int> &a , int l , int r)
{
    if(l > r)
        return NULL;
    if(l == r)
        return new BSTNode(a[l]);
    int mid = (l + (r - l) / 2);
    BSTNode* head = new BSTNode(a[mid]);
    head->left = convertArrayToBST(a , l , mid - 1);
    head->right = convertArrayToBST(a , mid + 1 , r);
    return head;
}

BSTNode* sortedArrayToBST(vector<int>& a)
{
    int n = a.size();
    return convertArrayToBST(a , 0 , n - 1);
}

void preorder(BSTNode* head)
{
    if(!head)
        return;
    cout << head->value << " ";
    preorder(head->left);
    preorder(head->right);
}


int main()
{
    vector <int> a = {-4 , 0 , 1 , 2 , 7};
    BSTNode* head = sortedArrayToBST(a);
    preorder(head);
    return 0;
}

Java解决方案,将已排序的数组转换为二进制搜索树

class BSTNode
{
    int value;
    BSTNode left , right;
    BSTNode(int x)
    {
        value = x;
        left = null;
        right = null;
    }
}

class convert_array_to_BST
{
    public static void main(String args[])
    {
        int[] a = {-4 , 0 , 1 , 2 , 7};
        BSTNode head = sortedArrayToBST(a);
        preorder(head);
    }

    static BSTNode convertArrayToBST(int[] a , int l , int r)
    {
        if(l > r)
            return null;
        if(l == r)
            return new BSTNode(a[l]);
        int mid = (l + (r - l) / 2);
        BSTNode head = new BSTNode(a[mid]);
        head.left = convertArrayToBST(a , l , mid - 1);
        head.right = convertArrayToBST(a , mid + 1 , r);
        return head;
    }

    static BSTNode sortedArrayToBST(int[] a)
    {
        return convertArrayToBST(a , 0 , a.length - 1);
    }

    static void preorder(BSTNode head)
    {
        if(head == null)
            return;
        System.out.print(head.value + " ");
        preorder(head.left);
        preorder(head.right);
    }
}
1 -4 0 2 7

将排序数组转换为二叉搜索树Leetcode解决方案的复杂性分析  

时间复杂度

上), N =树中元素的数量。 我们访问每个元素以构造BST并打印预遍历。

参见
从三个不同的数组中找出三个元素,使得a + b + c =和

空间复杂度

哦), 其中H =树的高度= 登录N。 在这两个递归函数中,我们确保树是高度平衡的。因此,我们使用最大 哦) 递归堆栈框架的空间。