669. 修剪二叉搜索树

function trimBST(root: TreeNode | null, low: number, high: number): TreeNode | null {
    if (root === null) {
        return null;
    }

    if (root.val > high) {
        return trimBST(root.left, low, high);
    }

    if (root.val < low) {
        return trimBST(root.right, low, high);
    }

    root.left = trimBST(root.left, low, high);
    root.right = trimBST(root.right, low, high);
    return root;
};

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

function sortedArrayToBST(nums: number[]): TreeNode | null {
    const buildTree = (nums: number[], left: number , right: number) => {
        if (left > right) {
            return null;
        };

        let mid = Math.floor(left + (right - left) / 2);
        let root = new TreeNode(nums[mid]);
        root.left = buildTree(nums, left, mid - 1);
        root.right = buildTree(nums, mid + 1, right);
        return root;
    };
    return buildTree(nums, 0, nums.length - 1);
};

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

function convertBST(root: TreeNode | null): TreeNode | null {
    let sum = 0;

    const dfs = (node: TreeNode | null) => {
        if (node) {
            dfs(node.right);
            node.val += sum;
            sum = node.val;
            dfs(node.left);
        }
    }
    dfs(root);
    return root;
};