leetcode--Validate Binary Search Tree--중점
2486 단어 LeetCode
두 갈래 나무의 문제는 차례로 돌아갈 생각을 해야 한다.여기서 쉽게 떠오르는 것은 좌우 나무가 모두 존재한다면,
if root.left.val < root.val < root.right.val:
return self.isValidBST(root.left) and self.isValidBST(root.right)하지만 사실은 그렇지 않다. 케이스[10,5,15,null,null,620]를 보자.여기 루트 10의rightsubtree도valid이지만 그중 6은 10보다 작습니다.그래서 이런 생각은 틀렸다.
여기 참조http://www.cnblogs.com/zuoyuan/p/3747137.html.
다음과 같은 코드가 있습니다. 교묘하게 이 코드의 최대치 최소치는 2147483647과 2147483648이어야 합니다.조금 작은 하계와 조금 큰 상계를 선택해야 한다. 그렇지 않으면[2147483647] 이 케이스는 지나갈 수 없다. 편의를 위해 10*10>2147483647과-10*1<-214748483648,
참고http://chaoren.is-programmer.com/posts/42736.html
class Solution:
# @param root, a tree node
# @return a boolean
def ValidBST(self, root, min, max):
if root == None:
return True
if root.val <= min or root.val >= max:
return False
return self.ValidBST(root.left, min, root.val) and self.ValidBST(root.right, root.val, max)
def isValidBST(self, root):
return self.ValidBST(root, -2147483648, 2147483647)
#return self.ValidBST(root, -10**10, 10**10)이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
python 문자열 입력으로 모든 유효한 IP 주소 생성(LeetCode 93번 문제)이 문제의 공식 난이도는 Medium으로 좋아요 1296, 반대 505, 통과율 35.4%를 눌렀다.각 항목의 지표로 말하자면 보기에는 약간 규범에 맞는 것 같지만, 실제로도 확실히 그렇다.이 문제의 해법과 의도는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
