查看: 376|回复: 7
收起左侧

[Leetcode] 弱问leetcode 98. Validate Binary Search Tree

|只看干货
Alpha256 | 显示全部楼层 |阅读模式
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (1)
 
 
0% (0)    👎

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
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大米 +3 收起 理由
14417335 + 3

查看全部评分


上一篇:求助一道路径的问题
下一篇:leetcode- 新人刷题
lkean9 2021-7-22 02:08:05 来自APP | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (47)
 
 
2% (1)    👎
(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 。

评分

参与人数 1大米 +4 收起 理由
14417335 + 4

查看全部评分

回复

使用道具 举报

 楼主| Alpha256 2021-7-22 02:49:09 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (1)
 
 
0% (0)    👎
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 了
回复

使用道具 举报

thrillerの空 2021-7-22 09:56:02 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (60)
 
 
1% (1)    👎
不行,题主你的代码思路有点混论了哦,你写这段代码究竟需要探究BST什么的性质,或者想要干嘛哦?
lmax, rmin是用来看嘛的呢?

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

使用道具 举报

thrillerの空 2021-7-22 09:58:17 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (60)
 
 
1% (1)    👎
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'
回复

使用道具 举报

 楼主| Alpha256 2021-7-22 10:12:07 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (1)
 
 
0% (0)    👎
thrillerの空 发表于 2021-7-21 21:58
你这里的错误就是应该你把print放在Base case -> if root is None,才造成的,如果递归到root == None, ...

明白了!谢谢
回复

使用道具 举报

 楼主| Alpha256 2021-7-22 10:13:00 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (1)
 
 
0% (0)    👎
thrillerの空 发表于 2021-7-21 21:56
不行,题主你的代码思路有点混论了哦,你写这段代码究竟需要探究BST什么的性质,或者想要干嘛哦?
lmax, r ...

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

使用道具 举报

thrillerの空 2021-7-22 10:31:39 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (60)
 
 
1% (1)    👎
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)
复制代码



同理。

评分

参与人数 1大米 +5 收起 理由
14417335 + 5

查看全部评分

回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表