LeetCode:98.验证二叉搜索树

输入:
    2
   / \
  1   3
输出: true

输入:
    5
   / \
  1   4
     / \
    3   6
输出: false

class Solution {
    long pre = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        // 访问左子树
        if (!isValidBST(root.left)) {
            return false;
        }
        // 访问当前节点：如果当前节点小于等于中序遍历的前一个节点，说明不满足BST，返回 false；否则继续遍历。
        if (root.val <= pre) {
            return false;
        }
        pre = root.val;
        // 访问右子树
        return isValidBST(root.right);
    }
}

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

        TreeNode(int x) {
            val = x;
        }
    }
    public class TreeNode1 {
        Integer val;
        TreeNode1 left;
        TreeNode1 right;
        TreeNode1 parent;
        Boolean isLeftChild;

        TreeNode1(int val,TreeNode1 parent,Boolean isLeftChild) {
            this.val = val;
            this.parent=parent;
            this.isLeftChild=isLeftChild;
        }
    }

    public boolean isValidBST(TreeNode root) {
        if(null == root){
            return true;
        }
        Stack<TreeNode> nodeStack = new Stack<>();
        Stack<TreeNode1> nodeStack1 = new Stack<>();
        nodeStack.push(root);
        nodeStack1.push(new TreeNode1(root.val,null,null));
        while (!nodeStack.isEmpty()){
            TreeNode node = nodeStack.pop();
            TreeNode1 node1 = nodeStack1.pop();
            if(!isSearchTree(node1,node1.val)){
                return false;
            }
            if (node.right!=null){
                nodeStack.push(node.right);
                node1.right=new TreeNode1(node.right.val,node1,false);
                nodeStack1.push(node1.right);
            }
            if(node.left!=null){
                nodeStack.push(node.left);
                node1.left=new TreeNode1(node.left.val,node1,true);
                nodeStack1.push(node1.left);
            }
        }
        return true;
    }

    public boolean isSearchTree(TreeNode1 node,int val){
        if(null== node.parent){
            return true;
        }
        if (node.isLeftChild){
            if(val<node.parent.val){
                return isSearchTree(node.parent,val);
            }
        }else{
            if(val>node.parent.val){
                return isSearchTree(node.parent,val);
            }
        }
        return false;
    }