代码随想录算法训练营第17天 | 第六章 二叉树 part07

235. 二叉搜索树的最近公共祖先

相对于 二叉树的最近公共祖先 本题就简单一些了，因为 可以利用二叉搜索树的特性。

题目链接/文章讲解：[link]（https://programmercarl.com/0235.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E7%9A%84%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88.html ）
视频讲解：[link]（https://www.bilibili.com/video/BV1Zt4y1F7ww）
因为是有序树，所以 如果 中间节点是 q 和 p 的公共祖先，那么 中节点的数组 一定是在 [p, q]区间的。即 中节点 > p && 中节点 < q 或者 中节点 > q && 中节点 < p，我们从根节点搜索，第一次遇到 cur节点是数值在[q, p]区间中，即 节点5，此时可以说明 q 和 p 一定分别存在于 节点 5的左子树，和右子树中。
我们就从根节点溯源，都大就往左找，都小就往右找。第一个找到的说明介于两者之间。这就是公共祖先树。为什么不可能再往下找，如果再往下找，说明两个都比下面的结点小或者都大。但实际上，两个一个大一个小。不符合条件。
只要看懂下图为什么5是1和9的最近公共祖先。这题就很好理解了。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if( root->val>p->val&&root->val>q->val)return lowestCommonAncestor( root->left, p, q) ;if( root->val<p->val&&root->val<q->val)return lowestCommonAncestor( root->right, p, q);else return root; }
};

701.二叉搜索树中的插入操作

本题比想象中的简单，大家可以先自己想一想应该怎么做，然后看视频讲解，就发现 本题为什么比较简单了。

题目链接/文章讲解：[link]（https://programmercarl.com/0701.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E6%8F%92%E5%85%A5%E6%93%8D%E4%BD%9C.html）
视频讲解：[link]（https://www.bilibili.com/video/BV1Et4y1c78Y）

/*** 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* insertIntoBST(TreeNode* root, int val) {if (root == NULL) {           return new TreeNode(val);}if(root->val>val)root->left =  insertIntoBST(root->left, val);if(root->val<val)root->right=insertIntoBST(root->right, val);return root;}
};

这题确实不难，因为它只让你插入，不管是不是平衡树或者树的的结构，所以，我们就一遍遍找，大了找左边，右边的肯定都比插入的大，不用管他们，小了找右边，左边的肯定都比插入的小，也不用管他们。一层层的把树的主干拆掉，肯定能找到适合的枝干插入叶子。另外，我在写的时候也在思考，前一个结点如何指向叶子节点的问题，其实也很好解决，直接返回给左右结点指针即可。如果下一个结点不是空结点，返回当前结点，是空结点，返回新的结点。写代码时越写越乱，后来整理就发现其实也不是很难，思路很清晰。

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

相对于 插入操作，本题就有难度了，涉及到改树的结构

题目链接/文章讲解：[link]（https://programmercarl.com/0450.%E5%88%A0%E9%99%A4%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E8%8A%82%E7%82%B9.html ）
视频讲解：[link]（https://www.bilibili.com/video/BV1tP41177us）
有以下五种情况：

第一种情况：没找到删除的节点，遍历到空节点直接返回了，完全不需要思考
找到删除的节点
第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点，最简单的删除
第三种情况：删除节点的左孩子为空，右孩子不为空，删除节点，右孩子补位，返回右孩子为根节点，也很好理解，只有右孩子，右孩子得顶上去
第四种情况：删除节点的右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点，也很好理解，只有左孩子，左孩子得顶上去，三种和四种情况差不多，完全可以类比
第五种情况：左右孩子节点都不为空，则将删除节点的左子树头结点（左孩子）放到删除节点的右子树的最左面节点的左孩子上，返回删除节点右孩子为新的根节点。我想到的方法是：用右子树的最小节点代替它，并删除最小节点。还是和他们的方法有点不太一样。代码随想录给出的方法是把左子树移动到右子树最小值下面。
第五种情况有点难以理解，看下面动画：

   2                                                     /     \
1        7/     \5          9 /  \       /    \ 4   6      8     102/     \
1        8/     \5          9 /   \         \ 4      6          10    

然后就是代码实现了：

1. 利用二叉搜索树的性质，寻找要删除的节点：
   如果目标值比当前节点的值小，我们去左子树寻找。
   如果目标值比当前节点的值大，我们去右子树寻找。
   如果找到目标值，那就是我们要删除的节点。
2. 情况一，找不到，直接返回原根节点
3. 情况二，叶子节点，直接删掉
4. 情况三，情况四，只有一个子节点，让子结点代替父节点，并删除
5. 情况5：节点有两个子节点
   将删除节点的左孩子放到删除节点的右子树的最左面节点的左孩子上，要删除的节点的右孩子为新的根节点。右面顶替，左边依附
   当节点有两个子节点时，比较复杂。我们需要找到它的中序后继，也就是右子树中最小的节点来替代它。找到右子树中的最小节点。用这个最小节点的值替换要删除的节点。删除右子树中的最小节点。右边最小顶替中间。
   代码看着挺长，实际上只要先把框架搭好，最后一步步写代码
   
   

需要使用临时指针 TreeNode* tmp = root 来保存当前要删除的节点，因为我们先用一个临时指针 tmp 保存原本 root 所指向的节点，然后让 root 指向新的位置（即它的右子节点）。最后，释放掉 tmp，从而确保内存不会泄漏。

TreeNode* pre = root;
TreeNode* cur = root->right;
while (cur->left != nullptr) {pre = cur;cur = cur->left;
}
root->val = cur->val;
pre->left = nullptr;
delete cur;

我最开始写的代码块如上所示，报错误了有一个潜在的 heap-use-after-free 问题，程序在释放内存后尝试访问该内存地址。错误根源：
循环里找到右子树中最小的节点 (cur) 并将其值赋给 root，然后你删除了该最小节点。如果 cur 节点是 pre->left 的子节点（即 cur 有左孩子），pre->left 设置为 nullptr，然后删除 cur。但如果 cur 本身就是 root->right（即 cur 没有左孩子，而是直接在右子树的根），pre 将始终等于 root，那么 pre->left = nullptr; 实际上不会移除正确的链接，导致错误。
另外当找到右子树最小的节点（即 cur），你设置了 pre->left = nullptr;但这是不正确的处理方式。如果 cur 节点有右子树，那么你需要将pre->left 指向 cur->right 而不是简单地设置为 nullptr。
完整代码如下：还是需要点耗脑子。避坑。我的思路比较简单直白易懂，直接一个替代，但是会出现很多考虑不到的问题，但是代码随想录的方法就复杂（其实也没复杂多少），代码更好实现。

/*** 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 == nullptr) return root; if (root->val == key) {if (root->left == nullptr && root->right == nullptr) {     delete root;return nullptr;}    else if (root->left == nullptr) {auto retNode = root->right;delete root;return retNode;}else if (root->right == nullptr) {auto retNode = root->left;delete root;return retNode;}      else {TreeNode* cur = root->right; while(cur->left != nullptr) {cur = cur->left;}cur->left = root->left; TreeNode* tmp = root;  root = root->right;     delete tmp;             return root;}}if (root->val > key) root->left = deleteNode(root->left, key);if (root->val < key) root->right = deleteNode(root->right, key);return root;}
};