import apple.laf.JRSUIUtils;
/**
* Source : https://oj.leetcode.com/problems/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 ValidateBinarySearchTree {
public boolean validate (TreeNode root) {
return isValid(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
/**
* 先判断根节点是否满足 root.value > min && root.value < max，如果满足，再递归判断左右子树
*
* @param root
* @param min
* @param max
* @return
*/
public boolean isValid (TreeNode root, int min, int max) {
if (root == null) {
return true;
}
if (root.value > max || root.value < min) {
return false;
}
return isValid(root.leftChild, min, root.value) && isValid(root.rightChild, root.value, max);
}
/**
* 二叉搜索树的中序遍历结果是单调递增的，所以中序遍历的时候当前节点值大于上一个节点的值
* 注意：这里每次递归会改变lastMax的值，需要保存下来，所以这里需要一个类似指针的变量，不能直接使用Integer等包装类型
*
* @param root
* @param lastMax
* @return
*/
public boolean isValidByInorder (TreeNode root, TreeNode lastMax) {
if (root == null) {
return true;
}
if (!isValidByInorder(root.leftChild, lastMax)) {
return false;
}
if (lastMax.value >= root.value) {
return false;
}
lastMax.value = root.value;
return isValidByInorder(root.rightChild, lastMax);
}
public boolean validate1 (TreeNode root) {
TreeNode lastMax = new TreeNode(Integer.MIN_VALUE);
return isValidByInorder(root, lastMax);
}
public TreeNode createTree (char[] treeArr) {
TreeNode[] tree = new TreeNode[treeArr.length];
for (int i = 0; i < treeArr.length; i++) {
if (treeArr[i] == '#') {
tree[i] = null;
continue;
}
tree[i] = new TreeNode(treeArr[i]-'0');
}
int pos = 0;
for (int i = 0; i < treeArr.length && pos < treeArr.length-1; i++) {
if (tree[i] != null) {
tree[i].leftChild = tree[++pos];
if (pos < treeArr.length-1) {
tree[i].rightChild = tree[++pos];
}
}
}
return tree[0];
}
private class TreeNode {
TreeNode leftChild;
TreeNode rightChild;
int value;
public TreeNode(int value) {
this.value = value;
}
public TreeNode() {
}
}
public static void main(String[] args) {
ValidateBinarySearchTree validateBinarySearchTree = new ValidateBinarySearchTree();
System.out.println(validateBinarySearchTree.validate(validateBinarySearchTree.createTree(new char[]{'1','2','3','#','#','4','#','#','5'})) + "-------false");
System.out.println(validateBinarySearchTree.validate(validateBinarySearchTree.createTree(new char[]{'3','1','4'})) + "-------true");
System.out.println(validateBinarySearchTree.validate(validateBinarySearchTree.createTree(new char[]{'3','2','4','1','#'})) + "-------true");
System.out.println();
System.out.println(validateBinarySearchTree.validate1(validateBinarySearchTree.createTree(new char[]{'1','2','3','#','#','4','#','#','5'})) + "-------false");
System.out.println(validateBinarySearchTree.validate1(validateBinarySearchTree.createTree(new char[]{'3','1','4'})) + "-------true");
System.out.println(validateBinarySearchTree.validate1(validateBinarySearchTree.createTree(new char[]{'3','2','4','1','#'})) + "-------true");
}
}