时间戳

首页 > 解决方案 > 无法将值插入二叉搜索树

python - 无法将值插入二叉搜索树

问题描述

我在 BST 的插入功能上遇到了一些麻烦。

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

更准确地说，当我使用 Spyder 进行检查时， 的root值为NoneType object of bulitins module. 结果，我很确定我未能将值插入到树中。我怀疑这是由于NoneTyperoot 的原因，但即使我在运行代码之前尝试给 root 一个值root = TreeNode(3)then 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)

任何建议将不胜感激！

标签： pythonpython-3.xbinary-search-treenonetypeinsertion

解决方案

在递归调用的条件中存在错误（您不需要检查if root.left:，并且if root.right:因为在递归调用中您已经处理了无条件）以及仅在树的右侧而不是在树的左侧的返回语句，所以这就是它不工作的原因根据您的期望：

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

推荐阅读