专栏首页书山有路勤为径排序数组转换为二叉查找树

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

已知一个排序的数组,将该数组转换为一个高度平衡的二叉查找树。 平衡的定义: 二叉查找树中,任意节点的两颗子树高度差不超过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 条评论
登录 后参与评论

相关文章

  • 二叉查找树

    二叉查找树是一种数据结构,它是具有以下性质的二叉树: 1.若左子树不空,则左子树上所有结点的值均小于或等于它的根结点的值; 2.若右子数不空,则右子树上所有...

    小飞侠xp
  • k个排序链表的合并

    LeetCode 23. Merge k Sorted Lists 已知k个已排序链表头节点指针,将这k个链表合并,合并后仍为有序的,返 回合并后的头节点。

    小飞侠xp
  • ROS通信架构(上)

    在ROS的世界里,最小的进程单元就是节点(node)。一个软件包里可以有多个可执行文件,可执行文件在运行之后就成了一个进程(process),这个进程在ROS中...

    小飞侠xp
  • 2019年7月数据库流行度排行:Oracle王者归来获大幅增长

    2019 已然走过一半,DB-Engines 的数据库流行度排行榜 7 月出炉,这可以算是数据库流行度的半年报了。

    数据和云
  • 相克军_Oracle体系_随堂笔记001-概述

    2.metalink.oracle.com,如今已经改成:http://support.oracle.com

    Alfred Zhao
  • Oracle嘉年华:分布式存储解决方案

    在Oracle数据库领域,近年的优化工作主要围绕着存储系统展开和深入,由存储而闪存,由外存而内存,内圣而外王。而在业界,随着Exadata在一体化、闪存应用上的...

    数据和云
  • 二分搜索树实现

    在析构的时候,我们要释放节点内存,这颗BST树的所有节点内存释放是一个递归的过程,因此我们这里调用destroy递归函数,去递归释放节点内存。

    公众号guangcity
  • 补充下3月面试题(好未来、腾讯音乐、小药药)

    补充一下落下的3月份的面试题,关于春季面经可以看我的上文 。从出师不利、面面具挂,到拿到阿里2个offer

    zz_jesse
  • Oracle默认的用户名和密码是什么? 原

    alter user scott identified by tiger;alter user scott account unlock;

    拓荒者
  • NC和NO、耳机美标和欧标的区别

    NO是常开(NORMAL OPEN),就是通常即未通电状态下,是断开的,通电后在电磁线圈的作用下(吸合)处于闭合状态。NC是常闭(NORMAL CLOSE),就...

    233333

扫码关注云+社区

领取腾讯云代金券