95.Validate Binary Search Tree-验证二叉查找树（中等题）

本文主要是介绍95.Validate Binary Search Tree-验证二叉查找树（中等题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

验证二叉查找树

题目

给定一个二叉树，判断它是否是合法的二叉查找树(BST)
一棵BST定义为：

节点的左子树中的值要严格小于该节点的值。
节点的右子树中的值要严格大于该节点的值。
左右子树也必须是二叉查找树。
一个节点的树也是二叉查找树。
样例

一个例子：

上述这棵二叉树序列化为 {2,1,4,#,#,3,5}.
###题解###

使用中序遍历，当遍历完左子节点返回根节点后，lastVal存储的是左子节点值与根节点进行比较，当遍历右子节点时lastVal存储的是根节点值与右子节点进行比较。firstNode避免当仅有一个根节点且值等于Integer.MIN_VALUE时出现误判。

/*** Definition of TreeNode:* public class TreeNode {*     public int val;*     public TreeNode left, right;*     public TreeNode(int val) {*         this.val = val;*         this.left = this.right = null;*     }* }*/
public class Solution {/*** @param root: The root of binary tree.* @return: True if the binary tree is BST, or false*/private int lastVal = Integer.MIN_VALUE;private boolean firstNode = true;public boolean isValidBST(TreeNode root) {if (root == null) {return true;}if (!isValidBST(root.left)) {return false;}if (!firstNode && lastVal >= root.val) {return false;}firstNode = false;lastVal = root.val;if (!isValidBST(root.right)) {return false;}return true;}
}