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  of a node contains only nodes with keys less than the node's key.
• subtree
• 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.

Constraints:

• The number of nodes in the tree is in the range [1, 104].
• 231 <= Node.val <= 231 - 1

 

풀이

• 이진 트리의 노드 값은 항상 정해진 범위가 있으므로 이를 사용함

1. 노드가 None인 경우에는 True로 종료
2. 범위에 부합하지 않는 경우에는 False로 종료
3. 이진 트리이므로, 양쪽 노드가 전부 조건에 부합해야 즉 False가 하나라도 없어야 함

 

예시)

• min_c = 무한으로 초기화, max_c = 무한으로 초기화

1. 처음 root(5)의 왼쪽의 자식 노드(1)는 단순히 root(5)보다 작은 값을 가져야 함
   • 노드(1)의 범위 : min_c = 최소값(유지), max_c = 부모 값인 5로 변경
2. 처음 root(5)의 오른쪽 자식 노드(7)는 큰 값을 가져야 함
   • 노드(7)의 범위 : min_c = 부모 값인 5로 변경, max_c = 최대값(유지)
3. 노드(7)의 오른쪽 자식 노드(8)는 부모(7)보다 큰 값을 가져야 함
   • 노드(8)의 범위 : min_c = 부모 값인 7로 변경, max_c = 유지(최대값)
4. 노드(7)의 왼쪽 자식 노드(6)는 최소값인 노드(5)보다는 크고 부모(7)보다 작은 값을 가져야 함
   • 노드(6)의 범위 : min_c = 5(유지), max_c = 부모 값인 7로 변경

 

따라서, right.val는 최소 node.val과 최대 max의 범위를 가지고, left.val은 최소 min, 최대 node.val의 범위를 가짐