평가

결과: 2회 실패 후 성공
풀이시간: 50분

실패원인

실패 1: 가정을 잘못함(아이디어 틀림)
실패 2: long x = (int) -21억... - 100 해당 로직에서 오버플로우가 발생. int로 바꿔주는게 아니라 long으로 바꿔주면 됨

풀이

Left Sub Tree의 최대값 < 중앙값 < Right Sub Tree의 최솟값

풀이

코드가 난잡합니다.
Sub Tree에서 이진탐색트리가 아니게 되면 Exception을 발생시키는 방법으로 문제를 풀었습니다.
더 깔끔한 풀이는 해당 코드 밑에 첨부하도록 하겠습니다

**
 * 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 static final long INF = ((long) Math.pow(2, 31)) + 100;
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        try {
            findMax(root);
            return true;           
        } catch(RuntimeException e) {
            return false;
        }
    }

    public long findMax(TreeNode root) {
        if (root.left == null && root.right == null) {
            return root.val;
        }
        long leftMax = - INF;
        long rightMin = INF;
        if (root.left != null) {
            leftMax = findMax(root.left);
        }
        if (root.right != null) {
            rightMin = findMin(root.right);
        }

        if ((leftMax < root.val) && (root.val < rightMin)) {
            if (root.right != null) {
                return findMax(root.right);
            }
            return root.val;
        }

        throw new RuntimeException();    
    }

    public long findMin(TreeNode root) {
        if (root.left == null && root.right == null) {
            return root.val;
        }
        long leftMax = - INF;
        long rightMin = INF;

        if (root.left != null) {
            leftMax = findMax(root.left);
        }
        if (root.right != null) {
            rightMin = findMin(root.right);
        }

        if ((leftMax < root.val) && (root.val < rightMin)) {
            if (root.left != null) {
                return findMin(root.left);
            }
            return root.val;
        }
        throw new RuntimeException();   
    }
}

깔끔한 풀이

Long으로 변환할 필요 없어 성능도 잘 나온다.

/**
 * 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 isValidHelper(root, null, null);
    }

    public boolean isValidHelper(TreeNode root, Integer min, Integer max) {
        if (root == null) {
            return true;
        }
        // 최소값보다 더 작거나 같은 값이 나올 수 없다(오른쪽 Sub Tree으로 이동하면 최소값이 정해짐)
        if (min != null && root.val <= min) { 
            return false;
        }
        if (max != null && max <= root.val) {
            return false;
        }

        // 왼쪽 서브트리가 적절하다 == 모든 값이 root.val보다 작다 && 오른쪽 서브트리가 적절하다 == 모든 값이 root.val보다 크다
        return isValidHelper(root.left, min, root.val) && isValidHelper(root.right, root.val, max);
    }

}