算法训练day23 LeetCode669.108.538.

669.修剪二叉搜索树

题目

669. 修剪二叉搜索树 - 力扣（LeetCode）

题解

代码随想录 (programmercarl.com)

递归

不能单纯地由根节点的值直接删除单值，需要继续判断子节点是否符合条件

class Solution
{
public:
    TreeNode *trimBST(TreeNode *root, int low, int high)
    {
        if (root == NULL)
            return NULL;
        if (root->val < low)
        {
            TreeNode *right = trimBST(root->right, low, high);
            return right;
        }
        if (root->val > high)
        {
            TreeNode *left = trimBST(root->left, low, high);
            return left;
        }
        root->left = trimBST(root->left, low, high);
        root->right = trimBST(root->right, low, high);
        return root;
    }
};

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

题目

108. 将有序数组转换为二叉搜索树 - 力扣（LeetCode）

题解

代码随想录 (programmercarl.com)

递归

从数组中取中点，不断切割数组递归地构造树符合平衡二叉树的定义


class Solution
{
private:
    TreeNode *traversal(vector<int> &nums, int left, int right)
    {
        if (left > right)
            return NULL;
        int mid = left + ((right - left) / 2);
        TreeNode *root = new TreeNode(nums[mid]);
        root->left = traversal(nums, left, mid - 1);
        root->right = traversal(nums, mid + 1, right);
        return root;
    }

public:
    TreeNode *sortedArrayToBST(vector<int> &nums)
    {
        TreeNode *root = traversal(nums, 0, nums.size() - 1);
        return root;
    }
};

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

题目

538. 把二叉搜索树转换为累加树 - 力扣（LeetCode）

题解

代码随想录 (programmercarl.com)

递归

因为二叉搜索树是有序的，每个节点的新值等于右侧子树的旧值总和--->以右左中遍历做累加

class Solution
{
private:
    int pre = 0;
    void traversal(TreeNode *cur)
    {
        if (cur == NULL)
            return;
        traversal(cur->right);
        cur->val += pre;
        pre = cur->val;
        traversal(cur->left);
    }

public:
    TreeNode *convertBST(TreeNode *root)
    {
        pre = 0;
        traversal(root);
        return root;
    }
};