package leetcode;

import java.util.ArrayList;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;

/**
 * https://leetcode.com/problems/validate-binary-search-tree/
 */
public class Problem98 {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public boolean isValidBST(TreeNode root) {
        List<Integer> values = new ArrayList<>();
        inOrder(root, values);
        Set<Integer> sortedValues = new TreeSet<>();
        for (int v : values) {
            sortedValues.add(v);
        }
        return values.equals(new ArrayList<>(sortedValues));
    }

    private void inOrder(TreeNode node, List<Integer> values) {
        if (node == null) {
            return;
        }
        inOrder(node.left, values);
        values.add(node.val);
        inOrder(node.right, values);
    }
}

@@ -16,108 +16,8 @@
 e;%0A%0A
-import java.util.ArrayList;%0Aimport java.util.List;%0Aimport java.util.Set;%0Aimport java.util.TreeSet;%0A%0A
 /**%0A
@@ -330,267 +330,112 @@
     
-List%3CInteger%3E values = new ArrayList%3C%3E();%0A        inOrder(root, values);%0A        Set%3CInteger%3E sortedValues = new TreeSet%3C%3E(
+return inOrder(root, new IntRef()
 );%0A    
+%7D%0A%0A
     
-for (int v : values) %7B%0A            sortedValues.add(v);%0A        %7D%0A        return values.equals(new ArrayList%3C%3E(sortedValues))
+private static class IntRef %7B%0A        private Integer val
 ;%0A  
@@ -455,12 +455,15 @@
 ate 
-void
+boolean
  inO
@@ -486,28 +486,18 @@
 de, 
-List%3CInteger%3E values
+IntRef ref
 ) %7B%0A
@@ -542,16 +542,21 @@
   return
+ true
 ;%0A      
@@ -558,32 +558,44 @@
        %7D%0A       
+ boolean a =
  inOrder(node.le
@@ -602,44 +602,164 @@
 ft, 
-values);%0A        values.add(
+ref);%0A        if (ref.val != null) %7B%0A            if (ref.val %3E= node.val) %7B%0A                return false;%0A            %7D%0A        %7D%0A        ref.val = 
 node.val
 );%0A 
@@ -754,17 +754,16 @@
 node.val
-)
 ;%0A      
@@ -763,16 +763,28 @@
 %0A       
+ boolean b =
  inOrder
@@ -800,15 +800,34 @@
 ht, 
-values)
+ref);%0A        return a & b
 ;%0A  

update problem 98