题目描述

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;
}