排序数组转换为二叉查找树
已知一个排序的数组，将该数组转换为一个高度平衡的二叉查找树。 平衡的定义： 二叉查找树中，任意节点的两颗子树高度差不超过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]
}
};本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018.06.17 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录