[LeetCode] 98. Validate Binary Search Tree - Java

https://leetcode.com/problems/validate-binary-search-tree/description/

Validate Binary Search Tree - LeetCode

---

문제

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

---

풀이

풀이 과정

이진 트리 root가 주어졌을 때 주어진 트리가 이진 탐색 트리인지 여부를 판단하는 문제이다.

이때 이진탐색트리의 정의는 다음과 같다

1. 노드의 왼쪽 서브트리는 모두 노드의 값보다 작은 값으로만 이루어진다.
2. 노드의 오른쪽 서브트리는 모두 노드의 값보다 큰 값으로만 이루어진다.
3. 왼쪽과 오른쪽 서브트리 역시 모두 이진탐색트리이다.

재귀를 통하여 풀이한다.

우선 재귀에 사용할 함수를 생성한다. 함수는 현재 노드와 현재 노드가 유효한 노드가 되는 최소값, 최대값을 인자로 받는다.
현재 노드가 null인 경우 모든 유효성 체크를 통과하고 마지막에 도달한 것이므로 true를 return한다.
현재 노드가 유효한 노드가 되는 최소값 이하인 경우 1번 정의에 어긋나므로 false를 return하고 반대로 최대값 이상인 경우에도 2번 정의에 어긋나므로 false를 return한다.
이후 왼쪽과 오른쪽 노드에 대해서 재귀적으로 탐색한다.
이 때 왼쪽노드를 탐색하는 경우 최대값을 현재 노드값으로 설정하고 오른쪽노드를 탐색하는 경우 최소값을 현재 노드값으로 설정한다.

public boolean isValid(TreeNode root, Integer min, Integer max){
    // 현재 노드가 null 이면 모든 유효성 체크를 통과해 마지막에 도달한 것이므로 true를 return
    if(root == null) return true;
    // 현재 노드가 유효한 노드가 되는 최소값 이하인 경우 false를 return
    if(min != null && root.val <= min) return false;
    // 현재 노드가 유효한 노드가 되는 최대값 이상인 경우 false를 return
    if(max != null && root.val >= max) return false;

    // 왼쪽, 오른쪽 노드에 대해 탐색
    return isValid(root.left, min, root.val) && isValid(root.right, root.val, max);
}

 

생성한 함수를 호출하여 정답을 return한다. 최초 root 노드를 호출할 때에는 최소값과 최대값을 각각 null로 설정한다.

public boolean isValidBST(TreeNode root) {
    return isValid(root, null, null);
}

---

최종 코드

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValid(root, null, null);
    }

    /**
     * @param root  트리의 root 노드
     * @param min   현재 노드가 유효한 노드가 되는 최소값
     * @param max   현재 노드가 유효한 노드가 되는 최대값
     * @return
     */
    public boolean isValid(TreeNode root, Integer min, Integer max){
        // 현재 노드가 null 이면 모든 유효성 체크를 통과해 마지막에 도달한 것이므로 true를 return
        if(root == null) return true;
        // 현재 노드가 유효한 노드가 되는 최소값 이하인 경우 false를 return
        if(min != null && root.val <= min) return false;
        // 현재 노드가 유효한 노드가 되는 최대값 이상인 경우 false를 return
        if(max != null && root.val >= max) return false;

        // 왼쪽, 오른쪽 노드에 대해 탐색
        return isValid(root.left, min, root.val) && isValid(root.right, root.val, max);
    }
}

---