leetcode_day23

今日任务：

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

669. 修剪二叉搜索树

题目：

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

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

思路：

根据day22的“删除二叉搜索树的节点”，这题就变成了：删除小于low的节点和大于high的节点，那么同样的做法，制定好分类讨论的规则，然后按规则遍历就好

可以中序遍历吗？

笔者第一版代码惨遭RE和WA，由于是区间，所以笔者“理所应当”地想要中序遍历先把小的全删了，然后再把大的全删了，看似没有问题，就像操作有序数组一样，但笔者实际写出的代码却是这样的：

TreeNode* trimBST(TreeNode* root, int low, int high) {
    if(root) {//不为空才操作
        root->left = trimBST(root->left, low, high);    //先左，中序嘛
        if(root->val < low) {                           //然后中，处理当前节点
            TreeNode * temp = root;                     //如果当前的小了
            root = root->right;                         //让更大一点的右孩子来补位（雷点所在）
            delete temp;                                //删掉当前的
        }
        else if(root->val > high) {                     //同理
            TreeNode * temp = root;
            root = root->left;                          //大了就让更小一点的左孩子来补位
            delete temp;
        }
        if(root) root->right = trimBST(root->right, low, high);//最后右
    }
    return root;
}

RE原因：这题力扣上似乎有点问题，对于[1, null, 2]这个用例，如果delete掉root，就会报错，但本地写好代码run出来是不会报错的，carl对此的解释是：

○ 代码加了内存释放，在运行时出错，[1,null,2] 这个输入，本地调试时，没有出错。卡哥的代码没有处理内存问题，难道这题不用自己释放内存？把delete的逻辑移除后，就通过了。手动delete反而会出错

○ 解答：因为最终答案是删除了原本的根节点，然后返回节点2作为新的根节点也就是答案，为此做了两个实验：1. 把right子树的指赋给原本的root，然后最终返回root，可以通过case；2. 把root指向right，然后之前用个tmp指向原本root的内存再删除，这次会报错。而报错的原因是释放的内存再次被使用，所以我猜测是LeetCode的判题机在判题的时候应该再次使用了原本子树根节点的那块内存导致的错误，你可以只删除那个会释放根节点的delete语句，其他的释放语句不去掉，结果还是可以通过的，所以你本地输出答案没有错误那说明就是lc自己的问题了，不用太过于纠结。

忽略力扣本身原因，关注上述中序代码的逻辑错误，即

WA原因：

对于用例[4, 2, 5, null, 3]，如下图所示，若范围为[4,5]，那么应该删除2、3，最后得到一棵4、5的链，但是依照上述代码，当递归到节点2时，会发生：

TreeNode * temp = root;           //记录节点2
root = root->right;               //将root->right赋值给root指针变量，意图让右孩子补位
delete temp;                      //删掉节点2

问题就出在第二条，原本计划让right来补位，但是实际操作却仅仅是给一个函数里的形式参数赋了值，相当于用形参root保留了当前的右儿子，之后递归处理右儿子right实际却处理了右孙子，可能会返回右孙子本身或者null，但是最后却返回了右儿子right，相当于跳过了if(root) root->right = trimBST(root->right, low, high);语句，会导致修剪不到位，对于上述用例，就会返回[3,4,5]，本应被删除的节点3被保留了。

看起来被否定的只是代码编写，而中序遍历这个思路似乎仍具有可行性，实际上，硬要保持左中右的教条中序遍历，也是可以的。

需要改的地方就是：如果根节点被删除，那么就应该返回 儿子节点 的 处理结果，而不仅仅是儿子节点，修改后的中序遍历如下，由于力扣本身原因，省去delete操作避免RE：

class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        //规则：
        //1. 当前小，删了让右孩子补位
        //2. 当前大，删了让左孩子补位
        //3. 当前合法，处理左右孩子后返回
        if(!root) return root;
        //左
        root->left = trimBST(root->left, low, high);
        //中
        if(root->val < low) 
            return trimBST(root->right, low, high);
        else if(root->val > high) 
            return root->left;
        else
            root->right = trimBST(root->right, low, high);
        return root;
    }
};

按照官解做完再看这段修改后的“中序”，其实会发现对比下来就是把root->left = trimBST(root->left, low, high);这句给摘出来提前了。

综上

对于“可以中序吗？”的问题，我的回答是可以，事实上这道题并不需要关注前中后序怎么遍历，这也引出了笔者的一个思维定势：二叉树的递归都基于前中后序遍历，迭代都基于层序遍历。不要局限于前中后序遍历，这只是参考，实际就按递归三部曲来就行

这也许是一直看卡哥的代码却没有仔细思考，光看了个大概长相的缘故。😣

正经解答

对一个小问题想多了，下面给出优雅的正确答案：

class Solution {
public:
    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. 将有序数组转化为二叉搜索树

乍一看，想要走捷径，直接拉个有序链表不也是二叉搜索树？

实际上题目要求平衡。。切

题目：

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

思路：

由于要平衡，所以对半分就行，这样深度差就得到控制，不会退化成链，有点像快排？

class Solution {
public:
    TreeNode *build(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 = build(nums, left, mid - 1);
        root->right = build(nums, mid + 1, right);
        return root;
    }
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return build(nums, 0, nums.size() - 1);
    }
};

官解整花活，划线方式给整了三种，实际就是一种方法

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

题目：

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

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

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

思路：

把累加树定义看懂就成，就是把一个节点右边的值（比它大的）全加起来变成这个节点的新值。那不就是从右至左累加么，一个右中左顺序遍历，开个int记录前一个节点的值。

class Solution {
public:
    int pre = 0;
    TreeNode* convertBST(TreeNode* root) {
        if(root == nullptr) return nullptr;

        root->right = convertBST(root->right);
        root->val += pre;
        pre = root->val;
        root->left = convertBST(root->left);

        return root;
    }
};

少有的直接秒杀还和标准答案一模一样，嘿嘿嘿😆