判断二叉搜索树

import java.util.*;


public class Solution {
    class Info{
        boolean isBST;
        int min;
        int max;
        Info(boolean isBst, int min, int max){
            this.isBST = isBst;
            this.min = min;
            this.max = max;
        }
    }
    public boolean isValidBST (TreeNode root) {
        // write code here
        if(root == null)
            return true;
        return process(root).isBST;
    }
    public Info process(TreeNode head){
        if(head == null)
            return null;
        Info leftInfo = process(head.left);
        Info rightInfo = process(head.right);
        
        int min = head.val;
        int max = head.val;
        
        if(leftInfo != null){
            min = Math.min(min, leftInfo.min);
            max = Math.max(max, leftInfo.max);
        }
        if(rightInfo != null){
            min = Math.min(min, rightInfo.min);
            max = Math.max(max, rightInfo.max);
        }
        
        boolean isBST = false;
        if(
            (leftInfo == null ? true : leftInfo.isBST )
            && 
            (rightInfo == null ? true : rightInfo.isBST)
            &&
            (leftInfo == null ? true : leftInfo.max < head.val)
            && 
            (rightInfo == null ? true : rightInfo.min > head.val)
        )
            isBST = true;
        
        return new Info(isBST, min, max);
    }
}

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return bool布尔型
     */
    public boolean isValidBST (TreeNode root) {
        // write code here
        if(root==null)
            return true;
        if(root.left!=null&&root.left.val>=root.val)
             return false;
        if(root.right!=null&&root.val>=root.right.val)
            return false;
        return isValidBST(root.left)&&isValidBST(root.right);
    }
}

public class Solution {

    class ReturnType {
        int max;
        int min;
        boolean isBST;
        public ReturnType(int max, int min, boolean isBST) {
            this.max = max;
            this.min = min;
            this.isBST = isBST;
        }
    }

    public boolean isValidBST(TreeNode root) {
        return process(root).isBST;
    }

    public ReturnType process(TreeNode x) {
        if (x == null) {
            return new ReturnType(Integer.MIN_VALUE, Integer.MAX_VALUE, true);
        }
        ReturnType leftData = process(x.left);
        ReturnType rightData = process(x.right);
        int max = Math.max(Math.max(leftData.max, rightData.max), x.val);
        int min = Math.min(Math.min(leftData.min, rightData.min), x.val);
        boolean isBST = leftData.isBST && rightData.isBST && x.val < rightData.min && x.val > leftData.max;
        return new ReturnType(max, min, isBST);
    }
}

    int a=-1;
    Stack<TreeNode> stack=new Stack<>();
    TreeNode node=root;
    while (!stack.isEmpty()||node!=null){
        while (node!=null){
            stack.add(node);
            node=node.left;
        }
        if (!stack.isEmpty()){
            node= stack.pop();
            if (a!=-1&&a>=node.val)
                return false;
            a=node.val;
            node=node.right;
        }
    }
    return true;

java代码

一开始遍历到一个数组中，然后判断这个数组是否等于它的排序数组，但发现题目中要求二叉树必须是严格递增的，也就是说[1, 1]不是一棵bst。所以只能一个一个的元素遍历判断了：

public class Solution {
    private ArrayList<Integer> vals = new ArrayList<>();

    public boolean isValidBST(TreeNode root) {
        midTraversal(root);
//        ArrayList<Integer> clone = Collections.sort((ArrayList<Integer>) vals.clone();
        for(int i = 0; i < vals.size() - 1; i++){
            if(vals.get(i) >= vals.get(i + 1))
                return false;
        }
        return true;
    }

    private void midTraversal(TreeNode root) {
        if (root == null)
            return;
        midTraversal(root.left);
        vals.add(root.val);
        midTraversal(root.right);
    }
}

public class Solution {
    TreeNode preNode = new TreeNode(Integer.MIN_VALUE);
    public boolean isValidBST(TreeNode root) {
        if (root == null)
            return true;
        boolean left = isValidBST(root.left);
        boolean cur = (root.val > preNode.val);
        preNode = root;
        boolean right = isValidBST(root.right);
        return left && cur && right;
    }
}

public class Solution {
    TreeNode preNode = new TreeNode(Integer.MIN_VALUE);
    public boolean isValidBST(TreeNode root) {
        if (root == null)
            return true;
        if (!isValidBST(root.left)) 
            return false;
        if (root.val <= preNode.val)
            return false;
        preNode = root;
        return isValidBST(root.right);

    }
}

//中序遍历，用一个flag标记顺序是否正确
    boolean flag = true;    
    TreeNode prenode;
    public boolean isValidBST(TreeNode root) {
        inorder(root);
        return flag;
    }

    public void inorder(TreeNode root){
        if(root == null) return;
        inorder(root.left);
        if(prenode != null){
            if(prenode.val >= root.val){
                flag = false;
            }
        }
        prenode = root;
        inorder(root.right);
    }

//方法1：每个结点都对应一个上限，一个下限。
public boolean isValidBST(TreeNode root) {
    return isValidRoot(root,Integer.MIN_VALUE,Integer.MAX_VALUE);
}
public boolean isValidRoot(TreeNode root,int lower,int upper){
    if(root==null) return true;
    if(root.val<=lower || root.val>=upper) return false;
    return isValidRoot(root.left,lower,root.val)
            && isValidRoot(root.right,root.val,upper);
}
//方法2：中序遍历，记录前一个结点，与当前结点的值比较。
public class Solution {
    TreeNode pre;
    boolean isValidBST=true;
    public boolean isValidBST(TreeNode root) {
        inTraversal(root);
        return isValidBST;
    }
    public void inTraversal (TreeNode root){
        if(root==null) return ;
        inTraversal(root.left);
        if(pre!=null&&pre.val>=root.val) isValidBST=false;
        pre=root;
        inTraversal(root.right);
    }
}

public class Solution {
    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;

        boolean judge = true;
        TreeNode leftMaxNode;
        TreeNode rightMinNode;
        if (root.left != null) {
            leftMaxNode = root.left;
            while (leftMaxNode.right != null) {
                leftMaxNode = leftMaxNode.right;
            }
            judge = judge && (leftMaxNode.val < root.val);
        }
        if (root.right != null) {
            rightMinNode = root.right;
            while (rightMinNode.left != null) {
                rightMinNode = rightMinNode.left;
            }
            judge = judge && (rightMinNode.val > root.val);
        }

        return judge && isValidBST(root.left) && isValidBST(root.right);

    }
}

import java.util.*;
public class Solution {
    public boolean isValidBST(TreeNode root) {
		List<TreeNode> list = new ArrayList<>();
		inorder(root, list);
		for (int i = 1; i < list.size(); i ++) {
			if(list.get(i).val <= list.get(i - 1).val) return false;
		}
		return true;
	}
	public static void inorder(TreeNode root, List<TreeNode> list) {
		if(root != null) {
			inorder(root.left, list);
			list.add(root);
			inorder(root.right, list);
		}
	}
}

public class Solution { public boolean isValidBST(TreeNode root) { return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    } public boolean isValidBST(TreeNode root, long minVal, long maxVal) { if (root == null) return true; if (root.val >= maxVal || root.val <= minVal) return false; return isValidBST(root.left, minVal, root.val) && isValidBST(root.right, root.val, maxVal);
    }
}