Validate Binary Search Tree BST가 유효한지 @LeetCode

사고방식: 상하한 한정으로 귀속
처음에는 귀속을 생각했지만 상하한선을 사용하는 방법을 생각하지 못했고,parent를 매개 변수로 하나 더 넣으면 결과가 매우 번거롭다.상하한선을 사용한 후 코드가 간결하고 또렷하다.

package Level3;

import Utility.TreeNode;

/**
 * Validate Binary Search Tree 
 * 
 *  Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.
confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.


OJ's Binary Tree Serialization:
The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.

Here's an example:
   1
  / \
 2   3
    /
   4
    \
     5
The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".
 *
 */
public class S98 {

	public static void main(String[] args) {
		TreeNode root = new TreeNode(3);
		TreeNode p1 = new TreeNode(1);
		TreeNode p2 = new TreeNode(5);
		TreeNode p3 = new TreeNode(0);
		TreeNode p4 = new TreeNode(2);
		TreeNode p5 = new TreeNode(4);
		TreeNode p6 = new TreeNode(6);
		
		root.left = p1;
		root.right = p2;
		p1.left = p3;
		p1.right = p4;
		p2.left = p5;
		p2.right = p6;
		System.out.println(isValidBST(root));
	}

	public static boolean isValidBST(TreeNode root) {
		return rec(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }
	
	//         ，        
	public static boolean rec(TreeNode root, int min, int max){
		if(root == null){
			return true;
		}
		
		//      
		if(root.val <= min || root.val >= max){
			return false;
		}
		
		//                 
		return rec(root.left, min, root.val) && rec(root.right, root.val, max);
	}
	
	
	
}

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isValidBST(TreeNode root) {
        return isBSTRec(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }
    
    public boolean isBSTRec(TreeNode root, int left, int right) {
        if(root == null) {
            return true;
        }
        if(root.val <= left || root.val >= right) {
            return false;
        }
        
        return isBSTRec(root.left, left, root.val) && isBSTRec(root.right, root.val, right);
    }
}