LeetCode 450.删除二叉搜索树中的节点和669.修建二叉搜索树思路对比 及heap-use-after-free问题解决

题目描述 

450.删除二叉搜索树中的节点

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

一般来说，删除节点可分为两个步骤：

1. 首先找到需要删除的节点；
2. 如果找到了，删除它。

示例 1:

输入：root = [5,3,6,2,4,null,7], key = 3
输出：[5,4,6,2,null,null,7]
解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
另一个正确答案是 [5,2,6,null,4,null,7]。

669.修建二叉搜索树

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

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

示例 1：

输入：root = [1,0,2], low = 1, high = 2
输出：[1,null,2]

示例 2：

输入：root = [3,0,4,null,2,null,null,1], low = 1, high = 3
输出：[3,2,null,1]

思路对比

450题目在处理的时候需要分为五种情况，因为它需要改变子树的结构并且改变的方式不唯一：

第一种是二叉搜索树中不存在要寻找的节点

第二种是需要删除叶子节点

第三种是要删除的节点只有左子叶，没有右子叶

第四种是只有右子叶，没有左子叶

第五种是最难处理的，左右子叶都有，加入上图中要删除的节点是7，对于这一种情况处理的方式是选择右子叶9作为新的代替7的节点，然后将5 4 6这一左子树移动到8底下，也就是9这个子树下最小的数字。从代码上编写，就是一直向左搜寻，搜寻到叶子节点为止，就找到8了。

而669题目中说不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。 可以证明，存在 唯一的答案 。这道题出现第五种情况时与上一题不同的地方在于，如果当前节点小于low，那么它的整个左子树都需要被裁剪，如果大于high，整个右子树也需要被裁减，所以它不需要像上一题的第五种情况一样，对整个树的结构进行大的改变。当前节点小于low，就直接将上一节点指向右子树（右子树的值也需要裁剪）

代码实现

450.删除二叉搜索树中的节点

/**
 * definition for a binary tree node.
 * struct treenode {
 *     int val;
 *     treenode *left;
 *     treenode *right;
 *     treenode() : val(0), left(nullptr), right(nullptr) {}
 *     treenode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     treenode(int x, treenode *left, treenode *right) : val(x), left(left), right(right) {}
 * };
 */
class solution {
public:
    treenode* deletenode(treenode* root, int key) {
        if(root == null) return null;
        if(root->val == key){
            if(root->left == null && root->right == null) return null;
            else if(root->left != null && root->right == null) return root->left;
            else if(root->right != null && root->left == null) return root->right;
            else{
                treenode* cur = root->right;
                while(cur->left){
                    cur = cur->left;
                }
                cur->left = root->left;
                return root->right;
            }
        }
        if(root->val > key){
            root->left = deletenode(root->left,key);
        }
        if(root->val < key){
            root->right = deletenode(root->right,key);
        }
        return root;
    }
};

669. 修剪二叉搜索树

/**
 * definition for a binary tree node.
 * struct treenode {
 *     int val;
 *     treenode *left;
 *     treenode *right;
 *     treenode() : val(0), left(nullptr), right(nullptr) {}
 *     treenode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     treenode(int x, treenode *left, treenode *right) : val(x), left(left), right(right) {}
 * };
 */
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;
    }
};

heap-use-after-free问题

开始解决669问题时完全套用450的思路，代码如下，出现了报错 

/**
 * definition for a binary tree node.
 * struct treenode {
 *     int val;
 *     treenode *left;
 *     treenode *right;
 *     treenode() : val(0), left(nullptr), right(nullptr) {}
 *     treenode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     treenode(int x, treenode *left, treenode *right) : val(x), left(left), right(right) {}
 * };
 */
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 == null && root->right == null) return null;
            else if(root->left != null && root->right == null) return root->left;
            else if(root->right != null && root->left == null) return root->right;
            else{
                treenode* cur = root->right;
                while(cur->left){
                    cur = cur->left;
                }
                cur->left = root->left;
                return root->right;
            }
        }
        root->left = trimbst(root->left,low,high);
        root->right = trimbst(root->right,low,high);
        return root;
    }
};

发现问题出现在尾节点root->left本来有值，但是现在将它的节点全都转移到其他地方了，要将这个尾节点指向null就行，修改代码如下：

else{
                treenode* cur = root->right;
                while(cur->left){
                    cur = cur->left;
                }
                cur->left = root->left;
                root->left = null;
                return root->right;
            }
        }