[LeetCode] 98. Validate Binary Search Tree

leetcode.com/explore/featured/card/top-interview-questions-easy/94/trees/625/

Explore - LeetCode

첫 번째 시도 ( Fail )

재귀함수를 써보려고 했는데, 결과적으로는 개별노드의 왼쪽/오른쪽 자식노드만 기준을 만족한다.

문제에 대한 이해가 부족했다.

class Solution {
    public boolean isValidBST(TreeNode root) {
        if (root.left != null || root.right != null){
            if (root.left != null && root.left.val >= root.val) {
                return false;
            }
            if (root.right != null && root.right.val <= root.val){
                return false;
            }
            if (root.left != null && root.right != null){
                return isValidBST(root.left) && isValidBST(root.right);
            }
        }
        return true;
    }
}

두 번째 시도 ( Success )

해당 트리가 정렬된 이진트리인지 (오름차순) true or false 리턴하는 것임을 깨달았다.

처음에는 List에 해당 수를 담고 꺼내보며 확인하려고 했는데, Stack이 좀 더 간편할 것 같아서 스택을 이용했다. 중위순회(inorder)를 하며 stack에 저장한 다음, 하나씩 꺼내보며 오름차순으로 정렬된 트리인지 확인했다.

class Solution {
    Stack<Integer> stack = new Stack<>();
    public void align(TreeNode root) {
        if (root != null){
            align(root.left);
            stack.push(root.val);
            align(root.right);
        }
    }

    public boolean isValidBST(TreeNode root) {
        align(root);
        while (!stack.isEmpty() && stack.size() > 1){
            int top = stack.pop();
            if (top <= stack.peek()){
                return false;
            }
        }
        return true;
    }
}

 

 

그 외 다른사람들의 풀이

 

1. recursive

public class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    
    public boolean isValidBST(TreeNode root, long minVal, long maxVal) {
        if (root == null) return true;
        if (root.val >= maxVal || root.val <= minVal) return false;
        return isValidBST(root.left, minVal, root.val) && isValidBST(root.right, root.val, maxVal);
    }
}

2. using stack

public boolean isValidBST(TreeNode root) {
   if (root == null) return true;
   Stack<TreeNode> stack = new Stack<>();
   TreeNode pre = null;
   while (root != null || !stack.isEmpty()) {
      while (root != null) {
         stack.push(root);
         root = root.left;
      }
      root = stack.pop();
      if(pre != null && root.val <= pre.val) return false;
      pre = root;
      root = root.right;
   }
   return true;
}