[leetcode] ValidateBinarySearchTree

package t;

import java.util.ArrayList;
import java.util.List;

/**
* <pre>
* 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.
* </pre>
* */
public class ValidateBinarySearchTree {

    public class TreeNode {
        int      val;
        TreeNode left;
        TreeNode right;

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

    public class Solution {
        public boolean isValidBST(TreeNode root) {
            List<Integer> values = new ArrayList<Integer>();
            walkTree(root, values);
            for (int i = 0; i < values.size() - 1; i++) {
                if (values.get(i) >= values.get(i + 1))
                    return false;
            }
            return true;
        }

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