题目描述
image.png
题解
- 二叉搜索树：对于任意一个节点，左子树中的值都小于等于该节点的值，右子树中的值都大于等于该节点的值
- 根据上述定义，又已知是升序数组，那么数组中心的值是根节点，数组左边的值组成左子树，数组右边的值组成右子树。
- 然后用递归的思想，左右两个子数组再按照上述规则构建左右子树。
注意点：
根据示例，对于下标范围为[begin, end]的数组，其中心应该用begin + (end - begin + 1) / 2计算，而不是begin + (end - begin) / 2计算
代码
#include <iostream>
#include <vector>
using namespace std;
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int val){
this->val = val;
this->left = NULL;
this->right = NULL;
}
};
class Solution {
public:
/**
*
* @param num int整型vector
* @return TreeNode类
*/
TreeNode* sortedArrayToBST(vector<int>& num) {
// write code here
return sortedArrayToBST(num, 0, num.size() - 1);
}
TreeNode* sortedArrayToBST(vector<int>& num, int begin, int end){
if (begin > end){
return NULL;
}
int mid = begin + (end - begin + 1) / 2;
TreeNode* root = new TreeNode(num[mid]);
root->left = sortedArrayToBST(num, begin, mid - 1);
root->right = sortedArrayToBST(num, mid + 1, end);
return root;
}
};
int main(){
vector<int> num = {-1, 0, 1, 2}; // C++11 feature
Solution s;
TreeNode* root = s.sortedArrayToBST(num);
cout << root->val << endl;
cout << root->left->val << endl;
cout << root->right->val << endl;
cout << root->left->left->val << endl;
delete root->left->left;
delete root->left;
delete root->right;
delete root;
return 0;
}
