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

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

1. 第一想法

1. 首先二叉搜索树一定是有序的。我们使用中序遍历，得到的记录链表一定是有序的。
2. 我们可以比普通二叉树更快地定位一个节点的位置。
3. 对于当前的根节点，我们可以迅速判定，p，q在同一侧还是在两侧，然后分别递归。
   1. 如果在root两侧，说明要么当前root就是唯一最近公共祖先的可能。
      1. 如果从左右两侧找到了对应的node, 那么一定是最近公共祖先。
      2. 如果没有找到，那么说明没有找到p或者没有找到q。但这不可能，因为题目规定了一定会存在在树中。
      3. 所以我们根本不需要找，我们只需要找到当前的满足pq在root两侧的返回的root。
   2. 在root同侧，则递归到这一侧去找。

# 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':
        if root is None:
            return None
        else:
            if (p.val <= root.val) and (q.val >= root.val):
                return root
            if (p.val >= root.val) and (q.val <= root.val):
                return root
            if (p.val <= root.val) and (q.val <= root.val):
                return self.lowestCommonAncestor(root.left, p, q)
            if (p.val >= root.val) and (q.val >= root.val):
                return self.lowestCommonAncestor(root.right, p, q)

2. 学习时长

26分钟。

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

1. 第一想法

不要重构二叉树，我直接二叉搜索，走到哪里是叶子，插在应该在的一侧就好。

# 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 insert(self, root, val):
        if root.val < val:
            if not root.right:
                root.right = TreeNode(val)
            else:
                self.insert(root.right, val)
        else:
            if not root.left:
                root.left = TreeNode(val)
            else:
                self.insert(root.left, val)

    def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if root is None:
            return TreeNode(val)
        else:
            self.insert(root, val)
            return root

2. 学习时长

14分钟。

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

1. 第一想法

倒也不难，如果找到了指定的节点，删除当前节点，让右子树（较大的子树）顶上当前的位置。 把左子树插入到右子树的最左侧叶子节点做它的左子树就好。

# 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 insert(self, left_child, right_child):
        if left_child.val < right_child.val:
            if not right_child.left:
                right_child.left = left_child
            else:
                self.insert(left_child, right_child.left)
            
    def delete(self, root, key):
        if root.val == key:
            if root.left and root.right:
                self.insert(root.left, root.right)
                return root.right
            elif root.left:
                return root.left
            else:
                return root.right
        elif root.val < key:
            if root.right:
                root.right = self.delete(root.right, key)
            return root
        elif root.val > key:
            if root.left:
                root.left = self.delete(root.left, key)
            return root
        else:
            return root
        return root

    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        if root is None:
            return None
        else:
            root = self.delete(root, key)
            return root

2. 看完文档

有一种很简便的做法就是，将目标节点和其右子树的最左侧节点进行交换。 再做一次遍历，这次找到的目标节点就在一颗右子树的最左侧，直接用None覆盖掉即可。

3. 学习时长

40分钟。

这篇好文章是转载于：学新通技术网