669. 修剪二叉搜索树、108. 将有序数组转换为二叉搜索树、538. 把二叉搜索树转换为累加树

669. 修剪二叉搜索树

题目描述：

给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。 可以证明，存在 唯一的答案 。

所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。

解答：

此题先得明确：递归处理，然后遇到 root->val < low || root->val > high 的时候直接return NULL，这样是不行的！

因为当前根节点不满足时其左右子树中可能有节点满足条件。

如下图（1-3区间）：

首先分两种情况：

1.根在范围内：

        递归去修剪左右子树

2. 根不在范围内：

        又分为两种情况：

        （1）根大于high

                直接访问根的左子树，并将左子树返回值作为根（无需再考虑右子树）

        （2）根小于low

                直接访问根的右子树，并将右子树返回值作为根（无需再考虑左子树）

代码实现：

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

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

题目描述：

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

解答：

高度平衡，有序数组

想到每次从数组最中间取值作为根节点，有点 二分法 的味道

那么为问题来了，如果数组长度为偶数，中间节点有两个，取哪一个？

取哪一个都可以，只不过构成了不同的平衡二叉搜索树。所以我取了low位置为根，另一个添加至其右侧即可。

然后就是递归进行求解，构造左右子树即可。

代码实现：

class Solution {
private:
    TreeNode* traversal(vector<int>& nums, int left, int right) {
        if (left > right) return nullptr;
        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. 把二叉搜索树转换为累加树

题目描述：

给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

提醒一下，二叉搜索树满足下列约束条件：

节点的左子树仅包含键 小于 节点键的节点。
节点的右子树仅包含键 大于 节点键的节点。
左右子树也必须是二叉搜索树。

解答：

看到这道题，首先注意到其实二叉搜索树，那就意味着有序。

有序和累加放在一起，一定会产生不一样的思路。

那应该怎么加呢？

比它大的，那就是从右到左加。

问题又来了，从右到左加应该怎么遍历？

从右往左，遍历次序是右中左，和中序遍历类似，只不过应该是 反中序遍历。

解题方法就很明确了，递归反中序遍历整棵树，每次加上上一个节点返回的和。

考虑递归三要素：

参数和返回值：访问整棵树无需返回值，参数为递归的节点

内部处理逻辑：中节点的处理逻辑就是让当前节点的数值加上前一个节点的数值

终止条件：遇到空就终止。

代码实现：

class Solution {
public:
    int pre_val = 0;
    void anti_inorder(TreeNode* root){
        if (root == NULL)
            return ;
        anti_inorder(root->right);
        root->val += pre_val;
        pre_val = root->val;
        anti_inorder(root->left);
    }
    TreeNode* convertBST(TreeNode* root) {
        anti_inorder(root);
        return root;
    }
};