使用预订遍历验证二进制树

Question

我正在寻找leetcode问题 98。验证二进制搜索树：

给定二进制树的root，确定它是否是有效的二进制搜索树（BST）。

a 有效的BST 定义如下：

• 节点的左子树仅包含键的节点小于节点键。
• 节点的右子树仅包含键的节点大于 节点键。
• 左右子树都必须是二进制搜索树。

下面提供的代码以使用预订遍历验证二进制树属性有什么问题？

# 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 isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        def preorder(root):
        
            if root.left!=None:
                if root.left < root.val:
                    preorder(root.left)
                else:
                    return False
            
        
            if root.right!=None:
                if root.right>root.val:
                    preorder(root.right)
                else:
                    return False
       
    t= preorder(root)
    return t!=False

它正在返回false的测试用例，其中root = [2,1,3]

Answer 1

仅在 时，您才需要穿越右sub-tree 。

       def preorder(root):
            if root.left!=None:
                if root.left < root.val:
                    preorder(root.left)
                else:
                    return False
            
        
            if root.right!=None (and left-sub-tree is valid):
                if root.right>root.val:
                    preorder(root.right)
                else:
                    return False

注意：我不知道Python。在检查右手树时了解评论。

Answer 2

几个问题：

• root.left＆lt; root.val将A node 与整数进行比较。这应该是root.left.val＆lt; root.val。右侧检查相同。

• 预订返回false在发生违规时，呼叫者会使递归调用忽略此返回值并愉快地继续。这是错误的。当递归调用返回false，并且本身返回false时，它应该停止遍历。

• 不是主要问题，而是预订返回false，它应该更好地返回true，因此您可以确定预订返回布尔值，不必对无需或将返回值明确比较false> false。

  。

• 该算法仅检查节点的直接子是否具有与父母价值不冲突的值，但这还不足以验证BST。 左子树中的所有值必须小于父母的价值，而不仅仅是左子女。因此，即使上述问题已解决，该算法也会错误地说该BST有效：

    4
   /
  1
   \ \
    9＆lt;  - 违规（由于4）
   

要解决最后一点，您需要修改算法：意识到当您在BST中深处时，就会有一个窗口< /em>在有效BST中的子树的值可以具有：有下限和上限。在上面的示例中，节点1的右子只能在范围内具有值（1，4）。

这是一个破坏者的实现：

类解决方案（对象）：
def isvalidbst（self，root）：
def预订（根，低，高）：
返回不root或（（
低＆lt; root.val＆lt;高
预订（left，low，low，root.val）和
预订（root.right，root.val，高）
）

返回预订（root，-float（“ inf”），float（“ inf”））