LeetCode: Validate Binary Search Tree

문제 풀이

유효한 BST는 하나의 node에서 왼쪽 sub tree의 모든 값들은 node의 값보다 작고, 오른쪽 sub tree의 모든 값들은 node의 값보다 커야한다.

그래서 나는 다소 무식한 방법이지만 왼쪽, 오른쪽 sub tree를 일일이 확인했다...ㅋㅋ
사실 다른 방법이 있을거 같았는데 재귀는 어려워...
나중에 재귀만 따로 모아서 풀어봐야겠다...

import java.util.*;
class Solution {
    public boolean isValidBST(TreeNode root) {
        Stack<TreeNode> s = new Stack<>();
        TreeNode cur = root;
        s.add(root);
        while(!s.isEmpty()) {
            TreeNode temp = s.pop();
            if(temp.left != null) {
                if(leftJudge(temp.left, temp.val) == false) {
                    return false;
                }
                s.add(temp.left);
            }
            if(temp.right != null) {
                if(rightJudge(temp.right, temp.val) == false) {
                    return false;
                }
                s.add(temp.right);
            }
        }
        return true;
    }
    
    public boolean leftJudge(TreeNode cur, int root) {
        Stack<TreeNode> s = new Stack<>();
        s.add(cur);
        while(!s.isEmpty()) {
            TreeNode temp = s.pop();
            if(temp.val >= root) {
                return false;
            }
            if(temp.left != null) {
                s.add(temp.left);
            }
            if(temp.right != null) {
                s.add(temp.right);
            }
        }
        return true;
    }
    
    public boolean rightJudge(TreeNode cur, int root) {
        Stack<TreeNode> s = new Stack<>();
        s.add(cur);
        while(!s.isEmpty()) {
            TreeNode temp = s.pop();
            if(temp.val <= root) {
                return false;
            }
            if(temp.left != null) {
                s.add(temp.left);
            }
            if(temp.right != null) {
                s.add(temp.right);
            }
        }
        return true;
    }
}