未能将值插入二叉搜索树

Question

我对BST 的插入功能有些疑惑。

这些代码运行之后似乎没有输出return；但是，我无法成功地将值插入到树中。

更准确的说，我用Spyder查的时候，root的值是NoneType object of bulitins module。结果，我很确定我无法将值插入到树中。而且我怀疑这是由于根的 NoneType 造成的，但即使我试图通过 root = TreeNode(3) 然后 Solution().insert(root, 5) 在代码运行之前给根赋值。我不确定如何解决这个问题。

请看下面的代码。

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

class Solution():    

    def insert(self, root, val):

        if root is None:
            root = TreeNode(val)
            return root
        else:
            if val <= root.val:
                if root.left:
                    root.left = self.insert(root.left, val)
            else:
                if root.right:
                    root.right = self.insert(root.right, val)
                return root


root = None
Solution().insert(root, 5)

如有任何建议，我们将不胜感激！！

Answer 1

有错误（你不需要检查if root.left:和if root.right:，因为在递归调用中你已经处理了none条件）在你的递归调用条件下 return 语句只在树的右侧而不是树的左侧，所以这就是为什么它没有按照你的期望工作：

def insert(self, root, val):

    if root is None:
        root = TreeNode(val)
        return root
    else:
        if val <= root.val:
            root.left = self.insert(root.left, val)
        else:
            root.right = self.insert(root.right, val)
        return root

这里是 link 的工作代码：link

未能将值插入二叉搜索树

Failed to insert value into Binary Search Tree

python

python-3.x

binary-search-tree

nonetype

insertion