使用预序遍历验证二叉树

Question

我正在查看LeetCode问题98。验证二进制搜索树：

给定二叉树的根，确定它是否是有效的二叉搜索树 （BST）。

有效的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

对于root=[2,1,3]的测试用例，它将返回False

Answer 1

几个问题：

>

root.left

尽管当存在冲突时，preorder返回False，但进行递归调用的调用方忽略此返回值并愉快地继续。这是错误的。当递归调用返回＜code＞False＜/code＞时，它应该停止遍历，并且它自己将＜code＞False＜/ccode＞返回给调用方。

不是主要问题，但由于preord返回False，在其余情况下，它应该更好地返回true，因此您可以确定preord返回布尔值，而不必处理无或将返回值显式与False进行比较。

该算法仅检查节点的直接子节点是否具有与父节点的值不冲突的值，但这不足以验证BST。左侧子树中的所有值都必须小于父树的值，不仅仅是左侧子树的值。所以即使上面的问题都解决了，这个算法也会错误地说这个BST是有效的:

  4
 /
1
 \
  9  <-- violation  (because of 4)

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

下面是一个作为扰流板的实现：

＜code＞类解决方案（对象）：def isValidBST（self，root）：defpreorder（root，low，high）：返回不是root或（low

Answer 2

只有当左子树有效时，才需要遍历右子树。

       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。在检查右子树时理解注释。