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

二叉树理论基础：

https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE

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

题目链接：https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/

思路:

遇到这个题目首先想的是要是能自底向上查找就好了，这样就可以找到公共祖先了。
后序遍历（左右中）就是天然的回溯过程，可以根据左右子树的返回值，来处理中节点的逻辑。
首先最容易想到的一个情况：如果找到一个节点，发现左子树出现结点p，右子树出现节点q，或者左子树出现结点q，右子树出现节点p，那么该节点就是节点p和q的最近公共祖先。即情况一：
在这里插入图片描述
同时，题目强调：二叉树节点数值是不重复的，而且一定存在 q 和 p。
但是很多人容易忽略一个情况，就是节点本身p(q)，它拥有一个子孙节点q§。情况二：

其实情况一和情况二代码实现过程都是一样的，也可以说，实现情况一的逻辑，顺便包含了情况二。

因为遇到 q 或者 p 就返回，这样也包含了 q 或者 p 本身就是公共祖先的情况。
具体来说，可以在代码中，慢慢体会。

当左子树和右子树都返回上来，不为空的情况下，就找到了。反之哪边找到了，就把结果层层回溯，返回给头结点。
在这里插入图片描述

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) return null;
        // 这一步会把情况2（公共祖先）也包含进去 直接返回root结点，不会再判断下面的了
        if(root == p || root == q)  return root;
        // 自底向上 => 后序遍历
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);
        if(left!= null && right != null)    return root;
        if(left == null && right!= null)    return right;
        if(left != null && right == null)   return left;
        // 都为空的情况
        return null;
    }

}

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

题目连接：https://leetcode.cn/problems/insert-into-a-binary-search-tree/

思路：

可以不考虑题目中提示所说的改变树的结构的插入方式。
只要按照二叉搜索树的规则去遍历，遇到空节点就插入节点就可以了。
在这里插入图片描述
例如插入元素10 ，需要找到末尾节点插入便可，一样的道理来插入元素15，插入元素0，插入元素6，需要调整二叉树的结构么？并不需要。

只要遍历二叉搜索树，找到空节点插入元素就可以了，那么这道题其实就简单了。、

同时，搜索树是有方向了，可以根据插入元素的数值，决定递归方向。

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if(root == null){
            root = new TreeNode(val);
        }
        if(root.val < val)  root.right = insertIntoBST(root.right,val);
        if(root.val > val)  root.left = insertIntoBST(root.left,val);
        return root;
    }
}

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

题目链接：https://leetcode.cn/problems/delete-node-in-a-bst/

思路：

搜索树的节点删除要比节点增加复杂的多，有很多情况需要考虑。
（1）没找到删除的结点，遍历到空结点直接返回
（2）左右孩子都为空（叶子结点），直接删除节点，返回NULL为根节点
（3）只有左孩子为空，或者只有右孩子为空，这个时候只需要让他的孩子直接补位，返回左/右孩子为根节点即可
（4）左右孩子都不为空，这个情况是最复杂的，这里看左子树和右子树都行，结果不是唯一的。这里我们将删除节点的左子树头结点（左孩子）放到删除节点的右子树的最左面节点的左孩子上，这样可以保证是在比他小一点点（最接近）的结点下，返回删除节点右孩子为新的根节点。

可以根据这个图来理解。
原数据：
在这里插入图片描述
删除后：

要删除的节点（元素7）的右孩子（元素9）为新的根节点。.

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        // 没找到的情况包含在这里
        if(root == null)    return root;
        if(root.val == key){
            // 左节点为空的情况
            if(root.left == null)
                return root.right;
            // 右节点为空的情况
            else if(root.right == null)
                return root.left;
            // 左不为空，右也不为空
            // 把右子树中最大的结点当做新的结点，把原来的左子树全都放在这个结点下
            else{
                TreeNode tmp = root.right;
                while(tmp.left!=null)
                    tmp = tmp.left;
                tmp.left = root.left;
                root = root.right;  // 原来的结点也要更新
                return root;
            }
        }

        if(root.val > key)  root.left = deleteNode(root.left,key);
        if(root.val < key)  root.right = deleteNode(root.right,key);
        return root;
    }
}