98. Validate Binary Search Tree
Medium
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.
Example 1:
Input: root = [2,1,3] Output: true
Example 2:
Input: root = [5,1,4,null,null,3,6] Output: false Explanation: The root node's value is 5 but its right child's value is 4.
Constraints:
- The number of nodes in the tree is in the range
[1, 104]. -231 <= Node.val <= 231 - 1
문제설명
노드의 왼쪽 자식은 노드의 값보다 작아야하고, 노드의 오른쪽 자식은 노드의 값보다 커야합니다.
문제풀이
모든 노드를 확인해야 하는 완전 탐색의 문제이고, DFS 알고리즘을 이용하여 풀이하였습니다.
- 우선 DFS함수를 만들어줍니다. 매개변수로는 node, left, right를 받습니다.
def dfs(node, left, right):- 더 내려갈 곳이 없으면 True를 반환합니다.
if not node: return True- left와 right는 node의 val과 값을 비교하는 변수입니다. left는 node.val보다 작아야하고, right는 node.val보다 커야합니다.
if not (node.val < right and node.val > left):
return False- DFS함수를 재귀적으로 호출합니다. 왼쪽 자식과 오른쪽 자식을 차례대로 호출합니다.
return (dfs(node.left, left, node.val) and dfs(node.right, node.val, right))- DFS함수를 호출할 때 매개변수로 left는 음수의 무한대, right는 양수의 무한대로 설정합니다.
return(dfs(root, float("-inf"), float("inf")))전체코드
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
def dfs(node, left, right):
if not node:
return True
if not (node.val < right and node.val > left):
return False
return (dfs(node.left, left, node.val) and dfs(node.right, node.val, right))
return(dfs(root, float("-inf"), float("inf")))
to mist