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.

递归法

思路

遍历树, 用数组保存之前访问的节点, 如果之前访问的都小于当前访问的值那么树就是合理树

复杂度

时间 O(n) 空间 递归栈O(log)

代码

public boolean isValidBST(TreeNode root) {    if (root == null) {        return true;    }    ArrayList
    
      cur = new ArrayList
     
      ();    cur.add(null);    return helper(cur, root);}public boolean helper(ArrayList
      
        cur, TreeNode root) {    if (root == null) {        return true;    }    boolean left = helper(cur, root.left);    if (cur.get(0) != null) {        if (cur.get(0) >= root.val) {            return false;        }    }    cur.set(0, root.val);        boolean right = helper(cur, root.right);    return left && right;}