[ Tree ] 98. Validate Binary Search Tree

 

 

 

1. 문제

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

Validate Binary Search Tree - LeetCode

 

Given the root of a binary tree, determine if it is a valid binary search tree (BST).
주어진 이진트리가 유효한 이진탐색트리인지 결정하라. 유효한 BST는 다음과 같다.

A valid BST is defined as follows:

• The left  of a node contains only nodes with keys less than the node's key. = 왼쪽자식의 값은 root의 값보다 항상 작다 
• subtree = 하위트리가 있다
• The right subtree of a node contains only nodes with keys greater than the node's key. = 오른쪽자식의 값은 root의 값보다 항상 크다
• Both the left and right subtrees must also be binary search trees. 자식들의 하위 트리도 반드시 BST이어야 한다

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

 

 

2. 풀이

• 함무라비법전 버전
  • runtime : 23ms
  • beats : 5.74%
  • memory : 44.2MB
  • beats : 15.93%

/**
 * 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) {
        if(root == null){
            return true;
        }

	// boolean 변수 만들어서 
        boolean left = true;
        if(root.left != null && root.left.val >= root.val){
            left = false;
        }

        boolean right = true;
        if(root.right != null && root.right.val <= root.val){
            right = false;
        }

        
    // 오른쪽 자식의 왼쪽 자식 / 없으면 null
        TreeNode tempL = root.right != null ? root.right.left : null;
        while(tempL != null){
        // root node의 값이 오-왼 자식의 값과 같거나 크면 false
            if(root.val >= tempL.val){
                return false;
            }
            tempL = tempL.left;
        }

    // 왼쪽 자식의 오른쪽 자식 / 없으면 null
        TreeNode tempR = root.left != null ? root.left.right : null;
        while(tempR != null){
    // root node의 값이 왼-오 자식의 값과 같거나 작으면 false
            if(root.val <= tempR.val){ 
                return false;
            }
            tempR = tempR.right;
        }

    // boolean이 둘 다 true일 때 다음 자식 node들로 재귀 시작
        if(left && right){
            return isValidBST(root.left) && isValidBST(root.right);
        }else{
            return false;
        }
    }
}

 

 

 

 

• 풀이 2 - 함수 따로 작성 → runtime은 23에서 0으로 줄었지만 메모리 사용은 상승. 그치만 runtime 0 된 게 큰 장점 같음
  • runtime : 0ms
  • beats : 100%
  • memory : 44.4MB
  • beats : 9.2%

class Solution {
    public boolean isValidBST(TreeNode root) {
        return BST(root, Long.MIN_VALUE, Long.MAX_VALUE); // Long 클래스가 갖는 최소값&최대값부터 시작
    }

    private boolean BST (TreeNode node, Long min, Long max){
        if(node == null){
            return true;
        }

        if(node.val <= min || node.val >= max){ // 여기서 걸리면 false고 넘어가면 재귀 시작
            return false;
        }

        if(BST(node.left, min, (long) node.val) && BST(node.right, (long) node.val, max)){
            return true;
        }

        return false;
    }
}