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

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

题目链接：. - 力扣（LeetCode）

文章讲解：代码随想录

视频讲解：二叉搜索树找祖先就有点不一样了！| 235. 二叉搜索树的最近公共祖先_哔哩哔哩_bilibili《代码随想录》算法公开课开讲啦！快来打卡！本期视频的文字讲解版在「代码随想录」刷题网站：programmercarl.com， 这里刷题顺序，详细题解，应有尽有！, 视频播放量 30361、弹幕量 334、点赞数 733、投硬币枚数 455、收藏人数 95、转发人数 30, 视频作者 代码随想录, 作者简介 哈工大师兄，在腾讯、百度搬过砖，代码随想录网站：programmercarl.com，相关视频：一起操作两个二叉树？有点懵！| LeetCode：617.合并二叉树，动态规划子序列问题经典题目 | LeetCode：1143.最长公共子序列，不仅双指针，还有代码技巧可以惊艳到你！ | LeetCode：501.二叉搜索树中的众数，单调队列正式登场！| LeetCode：239. 滑动窗口最大值，单调栈，经典来袭！LeetCode:42.接雨水，调整二叉树的结构最难！| LeetCode：450.删除二叉搜索树中的节点，梦破碎的地方！| LeetCode：15.三数之和，我更完了，你看完了吗？，你对二叉搜索树了解的还不够！ | LeetCode：98.验证二叉搜索树，队列的基本操作！ | LeetCode：225. 用队列实现栈https://www.bilibili.com/video/BV1Zt4y1F7ww?share_source=copy_web

思路： 由于搜索二叉树的性质，找到的第一个节点的值在所要查找的两个节点的值的区间内就是它们的最近公共祖先。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        if (root.val > p.val && root.val > q.val) {
            TreeNode left = lowestCommonAncestor(root.left, p, q);
            return left;
        } else if (root.val < p.val && root.val < q.val) {
            TreeNode right = lowestCommonAncestor(root.right, p, q);
                return right;
        } else {
            return root;
        }
    }
}

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

题目链接：. - 力扣（LeetCode）

文章讲解：代码随想录

视频讲解：原来这么简单？ | LeetCode：701.二叉搜索树中的插入操作_哔哩哔哩_bilibili《代码随想录》算法公开课开讲啦！快来打卡！本期视频的文字讲解版在「代码随想录」刷题网站：programmercarl.com， 这里刷题顺序，详细题解，应有尽有！, 视频播放量 26287、弹幕量 322、点赞数 649、投硬币枚数 398、收藏人数 75、转发人数 22, 视频作者 代码随想录, 作者简介 哈工大师兄，在腾讯、百度搬过砖，代码随想录网站：programmercarl.com，相关视频：自底向上查找，有点难度！ | LeetCode：236. 二叉树的最近公共祖先，不仅双指针，还有代码技巧可以惊艳到你！ | LeetCode：501.二叉搜索树中的众数，调整二叉树的结构最难！| LeetCode：450.删除二叉搜索树中的节点，你对二叉搜索树了解的还不够！ | LeetCode：98.验证二叉搜索树，普大喜奔！二叉树章节已全部更完啦！| LeetCode：538.把二叉搜索树转换为累加树，你修剪的方式不对，我来给你纠正一下！| LeetCode：669. 修剪二叉搜索树，一起操作两个二叉树？有点懵！| LeetCode：617.合并二叉树，Manacher 马拉车算法【力扣周赛 420】，梦开始的地方，Leetcode：1.两数之和，学透哈希表，map使用有技巧！，二叉搜索树中，需要掌握如何双指针遍历！| LeetCode：530.二叉搜索树的最小绝对差https://www.bilibili.com/video/BV1Et4y1c78Y?share_source=copy_web

思路：按插入的节点为叶子节点思路来插入。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    TreeNode pre = null;
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val);
        }
        insertNewNode(root, val);
        return root;
    }
    public void insertNewNode(TreeNode root, int val) {
        if (root == null) {
            TreeNode treeNode = new TreeNode(val);
            if (pre.val > val) {
                pre.left = treeNode;
            } else {
                pre.right = treeNode;
            }
            return;
        }
        pre = root;
        if (root.val > val) {  
            insertNewNode(root.left, val);
        }else {
            insertNewNode(root.right, val);
        }
    }
}

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

题目链接：. - 力扣（LeetCode）

文章讲解：代码随想录

视频讲解：调整二叉树的结构最难！| LeetCode：450.删除二叉搜索树中的节点_哔哩哔哩_bilibili

思路：1.如果要删除的节点是叶子节点，则直接删除。2.如果要删除的节点只有一个子树，另一颗子树为空，则返回它不为空的子树的根节点。3.如果要删除的节点左右子树都不为空，则将该节点的左子树位置变为右子树的最左边的叶子节点的左节点，然后返回要删除节点的右节点。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) {
            return root;
        }
        if (root.val == key) {
            if (root.right == null) {
                return root.left;
            }
            if (root.left == null) {
                return root.right;
            }
            TreeNode temp = root.right;
            while (temp.left != null) {
                temp = temp.left;
            }
            temp.left = root.left;
            return root.right;
        }
        if (root.val > key) {
            root.left = deleteNode(root.left, key);
        } else {
            root.right = deleteNode(root.right, key);
        }
        return root;
    }
}