本文主要是介绍LeetCode 450.删除二叉搜索树中的节点和669.修建二叉搜索树思路对比 及heap-use-after-free问题解决，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述
450.删除二叉搜索树中的节点
给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
一般来说，删除节点可分为两个步骤：
- 首先找到需要删除的节点；
- 如果找到了，删除它。
示例 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;}}这篇关于LeetCode 450.删除二叉搜索树中的节点和669.修建二叉搜索树思路对比 及heap-use-after-free问题解决的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
