解法都在代码里，不懂就留言或者私信
二叉树的递归套路，练练就习惯了
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {/**首先你应该直到什么是二叉搜索树，二叉搜索树的特征就是对于某个节点，如果左树存在则左树上最大的节点小于当前节点如果右树存在，右树上最小的节点大于当前节点那么对于二叉树的递归套路，我们需要向左右子树要三个信息：1.是不是二叉搜索树2.最小节点的值3.最大节点的值 */public boolean isValidBST(TreeNode root) {Info info = getInfo(root);return info.isBST;}public Info getInfo(TreeNode root) {/**如果是空就返回null */if(root == null) {return null;}/**最大值最小值先设置为root的值 */int minVal = root.val;int maxVal = root.val;/**目前没有发现违反二叉搜索树规则的地方，暂时认为它是 */boolean isBST = true;/**拿到左右子树的信息 */Info leftInfo = getInfo(root.left);Info rightInfo = getInfo(root.right);/**左树不为空根据左树信息加工自己的三个信息 */if(leftInfo != null) {minVal = Math.min(minVal, leftInfo.minVal);maxVal = Math.max(maxVal, leftInfo.maxVal);isBST = leftInfo.isBST && isBST && leftInfo.maxVal < root.val;}/**右树不为空根据右树的信息加工自己的三个信息 */if(rightInfo != null) {minVal = Math.min(minVal, rightInfo.minVal);maxVal = Math.max(maxVal, rightInfo.maxVal);isBST = rightInfo.isBST && isBST && rightInfo.minVal > root.val;}/**根据自己的三个信息构造Info并返回 */return new Info(minVal, maxVal, isBST);}static class Info {int minVal;int maxVal;boolean isBST;public Info(int minVal, int maxVal, boolean isBST) {this.minVal = minVal;this.maxVal = maxVal;this.isBST = isBST;}}
}
