669. 修剪二叉搜索树

如果节点的某一边不和条件，返回另一边

class Solution {
public:
    // 如果<val 返回右边的
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if (root == nullptr) return nullptr;
        if (root->val < low)
        {
            return trimBST(root->right, low, high);
        }
        else if (root->val > high)
        {
            return trimBST(root->left, low, high);
        }
        else
        {
            root->left = trimBST(root->left, low, high);
            root->right = trimBST(root->right, low, high);
            return root;
        }
    }
};

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

找到中间节点后构建树

class Solution {
public:
    // 找到中间的点作为父节点
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        TreeNode *root = dfs(nums, 0, nums.size() - 1);
        return root;
    }

    // 找到中间节点
    TreeNode* dfs(vector<int>&nums, int left, int right)
    {
        if (left > right) return nullptr;
        int mid = (left + right) / 2;
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = dfs(nums, left, mid - 1);
        root->right = dfs(nums, mid + 1, right);
        return root;
    }
};

538. 把二叉搜索树转换为累加树

右中左遍历

class Solution {
public:
    // 右中左
    int pre = 0;
    TreeNode* convertBST(TreeNode* root) {
        dfs(root);
        return root;
    }

    void dfs(TreeNode* root)
    {
        if (root == nullptr) return;
        dfs(root->right);
        pre += root->val;
        root->val = pre;
        dfs(root->left);
    }
};