98. Validate Binary Search Tree

문제

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

코드

dfs

import java.util.*;
/**
 * 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);
    }

    boolean isValid(TreeNode root){
        if(root == null)
            return true;
        if(!(isValid(root.left) && isValid(root.right)))
            return false;

        //1. root doesn't have any child
        if(root.left == null && root.right == null)
            return true;
        //2. root has only left child
        if(root.left != null && root.right == null){
            int leftMax = rightMostValue(root.left);
            if(leftMax < root.val)
                return true;
            return false;
        }
        //3. root has only right child
        if(root.left == null && root.right != null){
            int rightMin = leftMostValue(root.right);
            if(root.val < rightMin)
                return true;
            return false;
        }
        //4. root has childeren on both side
        int leftMax = rightMostValue(root.left);
        int rightMin = leftMostValue(root.right);

        if(leftMax < root.val && root.val < rightMin)
            return true;
        return false;
    }

    int leftMostValue(TreeNode root){
        if(root.left == null)
            return root.val;
        return leftMostValue(root.left);
    }

    int rightMostValue(TreeNode root){
        if(root.right == null)
            return root.val;
        return rightMostValue(root.right);
    }

}

iterative

import java.util.*;
/**
 * 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 iterative(root);
    }

    boolean iterative(TreeNode root){
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curNode = root;
        TreeNode prevNode;
        long min_t = Integer.MIN_VALUE-1L;
        long max_t = Integer.MAX_VALUE+1L;
        while(curNode != null || !stack.isEmpty()){
            while(curNode != null){
                if(!(min_t < curNode.val && curNode.val < max_t)){
                    return false;
                }
                max_t = (long)curNode.val;
                stack.push(curNode);
                curNode = curNode.left;
            }
            curNode = stack.pop();
            prevNode = curNode;
            curNode = curNode.right;
            min_t = (long)prevNode.val;
            if(stack.isEmpty())
                max_t = Integer.MAX_VALUE+1L;
            else{
                max_t = (long)stack.peek().val;
            }
        }
        return true;

    }    
}

피드백

• 처음엔 당연하게 dfs로 풀었다. 근데 이걸 반복문으로 푼 풀이가 있었다.
  • dfs의 경우 시간 복잡도가 O(NlogN), 반복문은 O(logN)
• 예전 모 기업 면접 문제로 '반복문으로 preorder traversal' 하는 게 있어서 바로 반복문으로 도전
• 어떻게 해야 BST에 맞는 노드인지 결정하는 것이 가장 어려운 일이었다. 다음과 같이 결정해서 ack를 받아낼 수 있었다.
  • 나는 노드의 min threshold, max threshold를 설정해서 모든 노드에 대해서 검사해줌
  • 근데 모범답안의 경우에는 pre의 오른쪽 조상, 또는 오른쪽 서브트리의 leftMostChild와 비교해서 답을 찾는다.
    • 생각해보면 /, \ 로 찾는 거긴 해서 트리의 모든 경우를 찾을 수 있을 것 같긴하지만 단순히 이걸로 정답을 낼 수 있다는게 와닿지는 않는다.
• 트리도 iteration으로 순회할 수 있는 이 방법을 잘 익혀두자.