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

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

class Solution(object):
    def traversal(self, cur, p, q):
        if cur is None:
            return cur
        if cur.val > p.val and cur.val > q.val:
            left = self.traversal(cur.left, p, q)
            if left is not None:
                return left
        if cur.val < p.val and cur.val < q.val:
            right = self.traversal(cur.right, p, q)
            if right is not None:
                return right
        return cur

    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        return self.traversal(root, p, q)

        

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

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def deleteNode(self, root, key):
        """
        :type root: Optional[TreeNode]
        :type key: int
        :rtype: Optional[TreeNode]
        """

        # 如果root为空，就返回root
        if root is None:
            return root
        # 删除根节点的4种情况：都是通过返回值的形式达到删除节点的目的
        if root.val == key:
            # 1：二叉树就一个根节点，那就返回空
            if not root.left and not root.right:
                return None
            # 2：根节点只有右子树，就返回右子树
            elif not root.left:
                return root.right
            # 3：根节点只有左子树，就返回左子树
            elif not root.right:
                return root.left
            # 4：根节点有左和右子树，因为满足左<根<右的条件，在右子树的某个左节点（该左节点没有左子树）下接左子树。
            else:
                cur = root.right
                while cur.left is not None:
                    cur = cur.left
                cur.left = root.left
                return root.right
        # 当待删除的节点非根节点时，用递归法
        if root.val < key:
            root.right = self.deleteNode(root.right, key)
        if root.val > key:
            root.left = self.deleteNode(root.left, key)
        return root