弱问leetcode 98. Validate Binary Search Tree

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

    The left subtree of a node contains only nodes with keys less than the node's key.
    The right subtree of a node contains only nodes with keys greater than the node's key.
    Both the left and right subtrees must also be binary search trees.

网上找了一个code,我增加了一些print加以理解，还是不明白

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        lmax=None
        rmin=None
        return self.solve(root,lmax,rmin)
   
    def solve(self,root,lmax,rmin):
        print('enter')
        print(root)   
#print(root.val)
        print('lmax',lmax,'rmin',rmin)

        if root is None:
            return True
        
        elif (lmax!=None and lmax<=root.val) or (rmin!=None and rmin>=root.val):
            
          #  print(root.val, lmax, rmin)            
            
            return False
        
        
        print('condition1', root.left, root.val,rmin)
        print('condition2', root.right, lmax, root.val)
        
        
        return self.solve(root.left,root.val,rmin) and self.solve(root.right,lmax,root.val)

Run code输出的结果是

our input
[2,1,3]
stdout
enter
TreeNode{val: 2, left: TreeNode{val: 1, left: None, right: None}, right: TreeNode{val: 3, left: None, right: None}}
lmax None rmin None
condition1 TreeNode{val: 1, left: None, right: None} 2 None
condition2 TreeNode{val: 3, left: None, right: None} None 2
enter
TreeNode{val: 1, left: None, right: None}
lmax 2 rmin None
condition1 None 1 None
condition2 None 2 1
enter
None
lmax 1 rmin None
enter
None
lmax 2 rmin 1
enter
TreeNode{val: 3, left: None, right: None}
lmax None rmin 2
condition1 None 3 2
condition2 None None 3
enter
None
lmax 3 rmin 2
enter
None
lmax None rmin 3

Output
true

我的问题是
(1) 为什么一开始(#print(root.val)) root.val 是none,不是输入的[2,1,3]，应该是2吗
(2) 为什么在condition1, root.val成了2

(3) 结合return self.solve(root.left,root.val,rmin)和    def solve(self,root,lmax,rmin):， root.val作为了lmax,这是相对而言比较标准的写法吗？觉得counterintuitive

（1） 最开始的print(root.val)输出的结果就是。你提供的输出没有显示是None阿，这行被你注释掉了，所以本来就不会print

（2）对的

（3）并不感觉违背直觉，lmax, rmin在这里代表当前root的母结点的值，所以当前root值必须小于lmax，也必须大于rmin。很合理呀。可以改一下变量名，我个人不喜欢大于leftmin, 小于rightmax这种名字，把自己都搞混了。你把lmax改成rightbound, rmin改成leftbound，可能会舒服些
另外我觉得没有什么标准不标准之说，写出来逻辑正确，复杂度合理不就行了。

补充内容 (2021-07-22 02:09 +08:00):
（1）输出的就是2 。

lkean9 发表于 2021-7-21 14:08
（1） 最开始的print(root.val)输出的结果就是。你提供的输出没有显示是None阿，这行被你注释掉了，所以本 ...

谢谢回复。(1)的地方如果我uncomment会过不去，提示

AttributeError: 'NoneType' object has no attribute 'val'
    print(root.val)
Line 18 in solve (Solution.py)
    return self.solve(root.left,root.val,rmin) and self.solve(root.right,lmax,root.val)
Line 37 in solve (Solution.py)
    return self.solve(root.left,root.val,rmin) and self.solve(root.right,lmax,root.val)
Line 37 in solve (Solution.py)
    return self.solve(root,lmax,rmin)
Line 11 in isValidBST (Solution.py)
    ret = Solution().isValidBST(param_1)
Line 56 in _driver (Solution.py)
    _driver()
Line 67 in <module> (Solution.py)

我理解成了none。奇怪的是，过了if elif,

1. print(root.val)

复制代码

就work 了

不行，题主你的代码思路有点混论了哦，你写这段代码究竟需要探究BST什么的性质，或者想要干嘛哦？
lmax, rmin是用来看嘛的呢？

这样我才好修改你的代码，否则实在看不懂代码向干嘛......

Alpha256 发表于 2021-7-22 02:49
谢谢回复。(1)的地方如果我uncomment会过不去，提示

你这里的错误就是应该你把print放在Base case -> if root is None，才造成的，如果递归到root == None，那你的root.val就会报错，而且IDE也给你提示了：

AttributeError: 'NoneType' object has no attribute 'val'

thrillerの空 发表于 2021-7-21 21:58
你这里的错误就是应该你把print放在Base case -> if root is None，才造成的，如果递归到root == None， ...

明白了！谢谢

thrillerの空 发表于 2021-7-21 21:56
不行，题主你的代码思路有点混论了哦，你写这段代码究竟需要探究BST什么的性质，或者想要干嘛哦？
lmax, r ...

这个代码是从leetcode的discussion里找的，我觉得相对看得明白一点，如何挑出思路清楚的代码呢？还是我要再看看数据结构的书和网页？

Alpha256 发表于 2021-7-22 10:13
这个代码是从leetcode的discussion里找的，我觉得相对看得明白一点，如何挑出思路清楚的代码呢？还是我要 ...

额，我的意思这个code是用来干嘛的额，没有注释，而且题主加了好多print把我绕晕了哦，加上我自己好久没有用Python了，把and看成了多个数值返回，尴尬了，哈哈哈，不好意思哦。你自己选取的代码，也要明白代码的目的是什么哦。

不过我又看了看，这段代码就是检查传进去的BST是否是合法的，方法就是：

我们分别找到左子树的lmax，那左子树不可能有比lmax更大的值了，有就是不合法的BST；
右子树同理，我们找到rmin，那右子树不可能有rmin更小的值了，有就是不合法的BST；

不知道你理解这个思路了么？那你的第一个和第二个疑问可以画一画递归流程图，你应该就能明白了。

第三问，不知道你的标不标准是什么意思哦，这段代码：

1. return self.solve(root.left, root.val, rmin) and self.solve(root.right, lmax, root.val)

复制代码

就是刚才思路的一个递归检查，

1.         if root is None:
   
2.             return True
   
3.         elif (lmax != None and lmax <= root.val) or (rmin != None and rmin >= root.val):
   
4.             return False

复制代码

这段就是base case，一个是合法的情况，一个是不合法的情况

1. self.solve(root.left, root.val, rmin

复制代码

这个就是把root.left之后的root，root.val就是当前我们找到的左子树的最大值，rmin原封不动传过去。另一边的

1. self.solve(root.right, lmax, root.val)

复制代码

同理。