[Leetcode] 0098. 이진 탐색 트리 검증

Python, C++, JavaScript, SQL 및 TypeScript의 다양한 LeetCode 솔루션을 살펴보세요. 여러 프로그래밍 언어로 인터뷰 준비, 학습 및 코드 연습에 적합합니다. Github 레포 링크

주어진 뿌리 이진 트리의 유효한 이진 검색 트리(BST)인지 확인.

에이 유효한 BST 다음과 같이 정의됩니다:

노드의 왼쪽 서브 트리에는 키가 있는 노드만 포함됩니다. 보다 작음 노드의 키.
노드의 오른쪽 서브 트리에는 키가 있는 노드만 포함됩니다. 보다 크다 노드의 키.
왼쪽과 오른쪽 서브트리도 모두 이진 검색 트리여야 합니다.

예시 1:

입력: 루트 = [2,1,3]
산출: 진실

예 2:

입력: 루트 = [5,1,4,null,null,3,6]
산출: 거짓
설명: 루트 노드의 값은 5이지만 오른쪽 자식 노드의 값은 4입니다.

제약:

트리의 노드 수는 범위 내에 있습니다. [1, 10 ⁴ ].
-2 ³¹ <= 노드.val <= 2 ³¹ - 1

파이썬

				
					# 시간 복잡도: O(n) # 공간 복잡도: O(n) import math from typing import Optional class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right class 해결책: def isValidBST(self, root: Optional[TreeNode]) -> bool: def dfs(node: Optional[TreeNode], low=-math.inf, high=math.inf): node가 None인 경우: True를 반환합니다.node.val이 low보다 작으면 False를 반환합니다.node.val이 high보다 크면 False를 반환합니다.dfs(node.left, low, node.val) and dfs(node.right, node.val, high) return dfs(root) class 해결책: def isValidBST(self, root: Optional[TreeNode]) -> bool: prev = [-math.inf] def dfs(노드: Optional[TreeNode], prev): 노드가 아닌 경우: True를 반환합니다. dfs(노드.left, prev)가 아닌 경우: False를 반환합니다. 노드.val이 prev[0]보다 작으면 False를 반환합니다. prev[0] = 노드.val을 반환합니다. dfs(노드.right, prev)를 반환합니다. dfs(root, prev)를 반환합니다. root1 = TreeNode(2) root1.left = TreeNode(1) root1.right = TreeNode(3) print(Solution().isValidBST(root1)) root2 = TreeNode(5) root2.left = TreeNode(1) root2.right = TreeNode(4) root2.right.left = TreeNode(3) root2.right.right = TreeNode(6) print(Solution().isValidBST(root2))

파이썬

관련 기사