前言

今天不是算法训练营的第二十天，依旧是猛追先前落下的进度，争取在开学前能够把任务完成。

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

题目链接：235. 二叉搜索树的最近公共祖先

题目描述：

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

思路

这道题与先前的二叉树的最近祖先类似，相比起来难度甚至更低一些，二叉搜索树本身就已经有一定顺序规律可观察到。在之前解决二叉树的最近祖先时，我们的想法是自底向上回溯查找，如果发现左子树中有p、右子树中有q，那么说明当前节点是公共祖先。

回到这道题目，由于这里是二叉搜索树，与先前不同，我们只需要当前节点的值是大于小于（一大一小）p、q的值就说明当前节点是公共祖先，如果同时小于就处理右子树，如果同时大于就处理左子树。

完整代码实现

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        while root:
            if root.val < p.val and root.val < q.val:
                return self.lowestCommonAncestor(root.right, p, q)
            elif root.val > p.val and root.val > q.val:
                return self.lowestCommonAncestor(root.left, p, q)
            else:
                return root
        return None

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

题目链接：701. 二叉搜索树中的插入操作

题目描述：

给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。

注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。

思路

这道题的思路比较简单些，大致可以理解为在二叉搜索树的搜索操作的基础上加一步插入，总体来说就是如果当前节点比目标值大就判断是否有左孩子，没左孩子就直接插入，如果有就递归进行下一轮查找，右孩子同理。

整体代码实现

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if not root or root.val == val:
            return TreeNode(val)
        
        elif root.val > val:
            if not root.left:
                root.left = TreeNode(val)
            else:
                self.insertIntoBST(root.left, val)
        elif root.val < val:
            if not root.right:
                root.right = TreeNode(val)
            else:
                self.insertIntoBST(root.right, val)
        return root

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

题目链接：450. 删除二叉搜索树中的节点

题目描述：

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

一般来说，删除节点可分为两个步骤：

1. 首先找到需要删除的节点；
2. 如果找到了，删除它。

思路

这道题目涉及改变二叉树的结构，相比前面的题目难度有所提升。

这里我们要对二叉搜索树进行删除操作，由于二叉搜索树性质特殊，我们需要分成以下几种情况进行讨论：

• 被删节点是叶子节点
• 被删节点有左子树没右子树或被删节点有右子树没左子树
• 被删节点同时具备左右子树

首先讨论被删节点是叶子节点的情况，如果被删节点是叶子节点，我们直接返回空就行，不需要额外操作。

然后是被删节点有左子树没右子树或被删节点有右子树没左子树的情况，我们只需要返回其剩下的子树接上就行。

最后是被删节点同时具备左右子树，这种情况相较之前就复杂一些了，我们需要找到右子树中的最左节点，将删除的节点值与最左节点值交换，这样构建出来的树符合二叉搜索树性质。

整体代码实现

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        if not root:
            return root
        if root.val == key:
            if not root.left and not root.right:
                return None
            elif not root.left:
                return root.right
            elif not root.right:
                return root.left
            else:
                cur = root.right
                while cur.left:
                    cur = cur.left
                cur.left = root.left
                return root.right
        if root.val > key:
            root.left = self.deleteNode(root.left, key)
        if root.val < key:
            root.right = self.deleteNode(root.right, key)
        return root

总结

果然，隔了一段时间之后再写回顾重新发现了很多第一遍过时没发现没考虑的问题，目前看来之前刷题的时候甚至有点水。

今天的题目前面两道还是比较好理解的，最后一道题目涉及到改变二叉树结构，这种题目难度相较于利用二叉树性质更难一些。