LeetCode108—Convert Sorted Array to Binary Search Tree
构建排序二叉树。
原题
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
给定一个递增序列,通过此序列构建一个平衡排序二叉树BST。
分析
一开始没注意
height balanced
关键字,想着直接迭代BST插入走你,这样肯定创建的二叉树是“一路向右”。此题的正确姿势是:由于BST的中序遍历是递增的,那么生成序列的中点为根,左边节点为左子树,右边节点为右子树,根据此,找到中点后,对左子树和右子树分别递归找到左子树和右子树。。
代码
class Solution {
private:
TreeNode* helper(vector<int>&nums, int left, int right)
{
if (left > right)
{
return NULL;
}
int mid = left + (right - left) / ;
TreeNode* root = new TreeNode(nums[mid]);
root->left = helper(nums, left, mid - );
root->right = helper(nums, mid + , right);
return root;
}
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
TreeNode*root = helper(nums, , nums.size() - );
return root;
}
};