(LeetCode) Validate Binary Search Tree

Validate Binary Search Tree

  • Explore : Interview > Top Interveiw Questions > Easy Collection
  • 분류 : Trees
  • 난이도 : Easy

Problem

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

1
2
Input: root = [2,1,3]
Output: true

Example 2

1
2
3
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, 10^4].
  • -2^31 <= Node.val <= 2^31 - 1

Solution

Exapnder
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
* Example:
* var ti = TreeNode(5)
* var v = ti.`val`
* Definition for a binary tree node.
* class TreeNode(var `val`: Int) {
* var left: TreeNode? = null
* var right: TreeNode? = null
* }
*/
class Solution {
fun isValidBST(root: TreeNode?): Boolean {
if (root == null) {
return true
}
if (root.left == null && root.right == null) {
return true
}
return recursive(root, null, null)
}

fun recursive(node: TreeNode?, min: Int?, max: Int?): Boolean {
if (node == null) {
return true
}
if (min != null && min <= node.`val`) {
return false

}
if (max != null && node.`val` <= max) {
return false
}
return recursive(node.left, node.`val`, max) && recursive(node.right, min, node.`val`)
}
}

Point of Thinking

  • 이진트리의 조건을 검증하기 위해 min값과 max값을 들고다니면서 재귀로 처리한다.