Validate Binary Search Tree leetcode

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.

bfs中序遍历整个树， 因为BST所以是递增的 

根据这一点我们只需要中序遍历这棵树，然后保存前驱结点，每次检测是否满足递增关系即可。注意以下代码我么用一个一个变量的数组去保存前驱结点，原因是java没有传引用的概念，如果传入一个变量，它是按值传递的，所以是一个备份的变量，改变它的值并不能影响它在函数外部的值，算是java中的一个小细节。

一次树的遍历，所以时间复杂度是O(n)，空间复杂度是O(logn)。

public class Solution {
    public boolean isValidBST(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        res.add(null);
        return helper(root, res);
    }
    public boolean helper(TreeNode root, ArrayList<Integer> res){
        if (root == null){
            return true;
        }
        boolean left = helper(root.left, res);
        if (res.get(0) != null && res.get(0) >= root.val){//显示left和root比， 存入root， 然后root和right比 存入right
            return false;
        }
        res.set(0, root.val);
        boolean right = helper(root.right, res);
        return left && right;
    }
}