【LeetCode】108. Convert Sorted Array to Binary Search Tree

Problem:

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

Solution:

复习一下BST的基本性质:简而言之,对于BST中任意结点x,若其有左右结点 l 或 r ,需满足 l.key ≤ x.key ≤ r.key

BST的性能(基本操作耗时)与树高成正比,可改进为较为高效的平衡二叉树,即保持整棵树左右均匀,任意左右子树高度差不大于1

如题将有序数组转化为二叉平衡树,可将数组从中间分成左右两部分,在分别对中间根节点赋值,左子树和右子树的确定用递归方法

Code:

//in C language

/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
struct TreeNode *createTree(int left,int right, int nums[]){
if(right-left<)
return NULL;
//if负责终止递归
int mid=(left+right)/;
struct TreeNode *root=(struct TreeNode*)malloc(sizeof(struct TreeNode));
root->val=nums[mid];
root->left=createTree(left,mid-,nums);
root->right=createTree(mid+,right,nums); return root;
} struct TreeNode* sortedArrayToBST(int* nums, int numsSize) {
return createTree(, numsSize-, nums);
}

ps:似乎是谷哥哥家的题目~加油!

上一篇:将金额数字转换为大写汉字的js函数


下一篇:LeetCode刷题笔录Add Binary