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

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

思考

平衡二叉查找树:任意节点的两颗子树高度差不超过1的二叉查找树。能否将数组转换为平衡为平衡二叉排序树,关键是确认数组元素按何种顺序插入至二叉查找树

分析

将数组[1,2,3,4,5,6,7,8,9]中的元素,组成平衡二叉查找树,需要以元素5为根结点,将1、2、3、4与6、7、8、9分为两个部分。 将[1、2、3、4]中的元素,组成平衡二叉查找树,需要以元素2或3为根结点。将1与3、4(或1、2、4)分为两部分;将[6、7、8、9]中的元素,组成平衡二叉查找树,需要以元素7或8为根节点。将6与8、9(或6、7与9)分为两部分。 结论:每次选取数组的中间元素插入二叉查找树,完成选择后将数组划分为左右两个数组,再递归的处理这两个数组,继续选择数组的中间元素进行处理。

算法设计

设置递归函数,preorder_insert(const std::vector<int> &nums, std::vector<TreeNode *> &node_vec) 该函数的作用是将nums数组进行划分,begin与end代表正在划分的区间右端点,每次寻找区间的中间数据生成二叉树节点,保存在node_vec中: 当划分区间左端点大于右端点时,return 计算中间点:mid = (begin + end)/2; 构建二叉树节点,节点值为nums[mid],保存至node_vec; 递归解决中间点mid的左右两边数组数据。

void preorder_insert(const std::vevotr<int> &nums, std::vector<TreeNode *> &node_vec, int begin , int end){
    if(begin > end){
        return ;
    }
    int mid = (begin + end) / 2;
    node_vec.push_back(new TreeNode(nums[mid]));
    preorder_insert(nums,node_vec,begin,mid-1);
    preorder_insert(nums,node_vec,mid+1,end);
}
class Solution{
public:
    TreeNode * sortedArrayToBST(std:;vector<int> & nums){
         if(nums.size() == 0){
              return NULL;
          }
          std::vector<TreeNode *> node_vec;
          preorder_insert(nums, node_vec,0,nums.size()-1);
          for(int i =1; i < node_vec.size(); i++){
              BST_insert(node_vec[0],node_vec[i])
          }
          return node_vec[0]
    }
};

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器学习和数学

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

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

3129
来自专栏刘君君

JDK8的ArrayList源码学习笔记

2887
来自专栏数据结构笔记

数据结构(六):树

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

972
来自专栏LanceToBigData

Java集合源码分析(一)ArrayList

前言   在前面的学习集合中只是介绍了集合的相关用法,我们想要更深入的去了解集合那就要通过我们去分析它的源码来了解它。希望对集合有一个更进一步的理解!   既然...

2696
来自专栏算法与数据结构

数据结构 单链表&顺序表

顺序表: 一般使用数组(C语言中的数组采用顺序存储方式。即连续地址存储)来描述。 优点:在于随机访问元素, 缺点:插入和和删除的时候,需要移动大量的元素。 链表...

47810
来自专栏JavaEdge

ArrayList源码解析(基于Java8)扩容删除

4537
来自专栏彭湖湾的编程世界

【算法】二叉查找树(BST)实现字典API

参考资料 《算法(java)》                           — — Robert Sedgewick, Kevin Wayne 《数据结...

5199
来自专栏Bingo的深度学习杂货店

Q108 Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a hei...

3243
来自专栏用户画像

6.3.2 B+树基本概念

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

992
来自专栏desperate633

LintCode 数组剔除元素后的乘积题目代码

定义B[i] = A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1], 计算B的时候请不要使用除法。

971

扫码关注云+社区

领取腾讯云代金券