题目描述 

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;}}