登录
  • #刷题

弱问‌‌‍‍‌‍‍‌‍‍‌‍‍‌‍‍‍‍‍‌‌‍‌‌‍‌‍‌‍‌‌‍leetcode 98. Validate Binary Search Tree

Alpha256
325
7
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
7条回复
热度排序

发表回复