立志重刷代码随想录60天冲冲冲！！——第二十一天

108.将有序数组转换为二叉搜索树

class Solution {
public:
    TreeNode* sortBST(vector<int>& nums, int l, int r) {
        if (l > r) return nullptr;
        int mid = l + (r - l) / 2;
        TreeNode* node = new TreeNode(nums[mid]);
        node->left = sortBST(nums, l, mid - 1);
        node->right = sortBST(nums, mid + 1, r);
        return node;
    }
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return sortBST(nums, 0, nums.size() - 1);
    }
};

108. 将有序数组转换为二叉搜索树

class Solution {
public:
    int sum = 0;
    void traversal(TreeNode* root) {
        if (root == nullptr) return; 
        traversal(root->left);
        sum += root->val;
        traversal(root->right);
        return;
    }

    void SumTree(TreeNode* node, int& sum) {
        if (node == nullptr) return;
        SumTree(node->left, sum);
        int temp = sum;
        sum -= node->val;
        node->val = temp;
        SumTree(node->right, sum);
        return;
    }

    TreeNode* convertBST(TreeNode* root) {
        traversal(root);
        SumTree(root, sum);
        return root;
    }
};