二进制搜索T的删除函数不返回

Question

我试图为BST定义一个delete函数，但遇到了一些麻烦。 在这个Solution类中有insert、find_max、search、preorder和delete函数。我希望使用这些函数删除元素，并通过删除node=3、8、21测试结果，然后打印输出。你知道吗

但是，我发现没有返回任何输出，并且BS Tree的值与我预期的不一样，这就是预期的结果：

我想知道这个麻烦可能是因为一些None值。你知道吗

以下是输入值：

root = None
s = Solution()
# 放入資料
root = s.insert(root, 10)
root = s.insert(root, 21)
root = s.insert(root, 6)
root = s.insert(root, 3)
root = s.insert(root, 8)
root = s.insert(root, 19)
root = s.insert(root, 24)
root = s.insert(root, 7)
root = s.insert(root, 15)
root = s.insert(root, 22)
root = s.insert(root, 20)
root = s.insert(root, 25)

root = s.delete(root, 3)  # where root is leaf node
root = s.delete(root, 8)  # where root is left tree
root = s.delete(root, 21) # where root is BST
s.preorder(root)

这是密码。你知道吗

class TreeNode():
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

class Solution():

    def insert(self, root, val):
        ...

    def search(self, root, target):

        # Pre-Order
        if root is None:
            return None
        else:
            if target == root.val:
                return root
            elif target < root.val:
                return self.search(root.left, target)
            else:
                return self.search(root.right, target)

    def find_max(self, root):

        now = root
        while now.right:
            now = now.right
        return now

    def delete(self, root, target):

        root = self.search(root, target)

        if root is None:
            return root
        else:
            if target == root.val:
                # when root is a leaf node
                if root.left is None and root.right is None:
                    root = None
                    return root

                elif root.left is None or root.right is None:
                    # when root is a left tree
                    if root.left:
                        root = root.left
                        return root

                    # when root is a right tree
                    else:
                        root = root.right
                        return root

                # when root is a BST
                elif root.left and root.right:
                    change_value = self.find_max(root.left)
                    root.val = change_value.val
                    root.left = self.delete(self, root.left, root.val)
                    return root


            else:
                return root

    # print the value of BST
    def preorder(self, root):
        if root is not None:
            print(root.val)
            self.preorder(root.left)
            self.preorder(root.right)

原始BST图像：

Answer 1

谢谢大家给了我一些线索！我发现上述问题的答案，关键是“递归”。为了考虑每个期望，我需要应用递归函数；因此，在这种上下文中可能无法应用search函数。你知道吗

下面是我应用递归概念并停止使用search函数后的代码：

class TreeNode():
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

class Solution():

    def insert(self, root, val):
        ...
    def search(self, root, target):
        # Pre-Order
        if root is None:
            return None
        else:
            if target == root.val:
                return root
            elif target < root.val:
                return self.search(root.left, target)
            else:
                return self.search(root.right, target)

    def find_max(self, root):

        now = root
        while now.right:
            now = now.right
        return now

    def delete(self, root, target):

        if root is None:
            return root
        else:
            if target < root.val:
                root.left = self.delete(root.left, target)
                return root
            elif target > root.val:
                root.right = self. delete(root.right, target)
                return root
            else:
                # where root is a leaf node
                if root.left is None and root.right is None:
                    root = None
                    return root
                if root.right is None or root.left is None:
                    # when root is a left tree
                    if root.left:
                        root = root.left
                        return root
                    # when root is a right tree
                    else:
                        root = root.right
                        return root
                # when root is a binary search tree
                elif root.left and root.right:
                    root.val = self.find_max(root.left).val
                    root.left = self.delete(root.left, root.val)
                    return root

    # print the outcome of the tree
    def preorder(self, root):
        if root is not None:
            print(root.val)
            self.preorder(root.left)
            self.preorder(root.right)


root = None
s = Solution()
root = s.insert(root, 10)
root = s.insert(root, 21)
root = s.insert(root, 6)
root = s.insert(root, 3)
root = s.insert(root, 8)
root = s.insert(root, 19)
root = s.insert(root, 24)
root = s.insert(root, 7)
root = s.insert(root, 15)
root = s.insert(root, 22)
root = s.insert(root, 20)
root = s.insert(root, 25)

# s.preorder(root)

最后，它似乎返回了正确的输出。你知道吗

10
6
3
8
7
20
19
15
24
22
25

欢迎任何意见！或者如果仍然有可能应用search函数来完成此尝试，请给我一些建议或提示！！你知道吗