代码随想录算法训练营第22天（二叉树8 | ● 235. 二叉搜索树的最近公共祖先 ● 701.二叉搜索树中的插入操作 ● 450.删除二叉搜索树中的节点

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

相对于 二叉树的最近公共祖先 本题就简单一些了，因为 可以利用二叉搜索树的特性。
题目链接/文章讲解：235. 二叉搜索树的最近公共祖先
视频讲解：235. 二叉搜索树的最近公共祖先

解题思路

只要从上到下去遍历，遇到 cur节点是数值在[p, q]区间中则一定可以说明该节点cur就是p 和 q的公共祖先。 且一定是最近公共祖先。
而递归遍历顺序，本题就不涉及到 前中后序了（这里没有中节点的处理逻辑，遍历顺序无所谓了）

总结

对于二叉搜索树的最近祖先问题，其实要比普通二叉树公共祖先问题 简单的多。
不用使用回溯，二叉搜索树自带方向性，可以方便的从上向下查找目标区间，遇到目标区间内的节点，直接返回。
最后给出了对应的迭代法，二叉搜索树的迭代法甚至比递归更容易理解，也是因为其有序性（自带方向性），按照目标区间找就行了。
本题与昨天二叉树的公共祖先一题思路还是有区别的。

• 本题是从上往下搜索，不涉及到回溯，前中后序遍历都可以；普通二叉树是从下往上搜索，涉及到回溯，需要中序遍历。
• 本题和上道题的递归函数都有返回值，区别是本题是搜索一条边，上题是搜索整棵树。

// 递归
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);
        return root;
    }
}

// 迭代
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
       while(true){
           if(root.val > p.val && root.val > q.val) root = root.left;
           else if(root.val < p.val && root.val < q.val) root = root.right;
           else break;
       } 
       return root;
    }
}

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

本题比想象中的简单，大家可以先自己想一想应该怎么做，然后看视频讲解，就发现 本题为什么比较简单了。
题目链接/文章讲解：701.二叉搜索树中的插入操作
视频讲解：701.二叉搜索树中的插入操作

解题思路

可以不考虑题目中提示所说的改变树的结构的插入方式。
要明确的一点是：我们一定可以在叶子节点找到要插入的位置。
如何通过递归函数返回值完成新加入节点的父子关系赋值操作呢：下一层将加入节点返回，本层用root->left或者root->right将其接住。

总结

首先在二叉搜索树中的插入操作，大家不用恐惧其重构搜索树，其实根本不用重构。
然后在递归中，我们重点讲了如何通过递归函数的返回值完成新加入节点和其父节点的赋值操作，并强调了搜索树的有序性。
最后依然给出了迭代的方法，迭代的方法就需要记录当前遍历节点的父节点了，这个和没有返回值的递归函数实现的代码逻辑是一样的。

// 有返回值的递归
class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        // 终止条件
        if(root == null) return new TreeNode(val); // 如果当前节点为空，也就意味着val找到了合适的位置，此时创建节点直接返回。
        if(root.val < val){
            root.right = insertIntoBST(root.right, val); // 递归创建右子树
        }else if(root.val > val){
            root.left = insertIntoBST(root.left, val);   // 递归创建左子树
        }
        return root;
    }
}

// 迭代
class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if(root == null) return new TreeNode(val);
        TreeNode newRoot = root;
        TreeNode pre = root;
        while(root != null){
            pre = root;
            if(root.val > val) {
               root = root.left; 
            }
            else if(root.val < val) {
               root = root.right; 
            }
        }
        if(pre.val > val) {
            pre.left = new TreeNode(val);
        }else{
            pre.right = new TreeNode(val);
        }
        return newRoot;
    }
}

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

相对于 插入操作，本题就有难度了，涉及到改树的结构
题目链接/文章讲解：450.删除二叉搜索树中的节点
视频讲解：450.删除二叉搜索树中的节点

解题思路

递归三部曲：

1. 确定递归函数参数及返回值
2. 确定终止条件，遇到空返回，其实这也说明没找到删除的节点，遍历到空节点直接返回了。
   if (root == nullptr) return root;
3. 确定单层递归的逻辑
   有以下五种情况：
   第一种情况：没找到删除的节点，遍历到空节点直接返回了
   找到删除的节点
   第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点
   第三种情况：删除节点的左孩子为空，右孩子不为空，删除节点，右孩子补位，返回右孩子为根节点
   第四种情况：删除节点的右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
   第五种情况：左右孩子节点都不为空，则将删除节点的左子树头结点（左孩子）放到删除节点的右子树的最左面节点的左孩子上，返回删除节点右孩子为新的根节点。

// 递归
class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if(root == null) return root; // 情况1
        if(root.val == key){
            if(root.left == null && root.right == null) return null;  // 2
            else if(root.left == null && root.right != null) return root.right;   // 3
            else if(root.left != null && root.right == null) return root.left;    // 4
            else{  // 5
                TreeNode cur = root.right;
                while(cur.left != null){
                    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;
    }
}