leetcode-75/450_delete_node_in_a_bst.py at main · ArtRabs/leetcode-75 · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
# LeetCode 450 Delete Node in a BST
# URL: https://leetcode.com/problems/delete-node-in-a-bst/
# Difficulty: Medium
# Language: Python 3.10+

# 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]
        """

        if not root:

            return None

        if root.val > key:

            root.left = self.deleteNode(root.left, key)

        elif root.val < key:

            root.right = self.deleteNode(root.right, key)

        else:

            if not root.left:

                return root.right

            elif not root.right:

                return root.left

            else:

                min_node = root.right

                while min_node.left:

                    min_node = min_node.left

                root.val = min_node.val

                root.right = self.deleteNode(root.right, min_node.val)

        return root