题解 | #判断是不是二叉搜索树#

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    // 封装要获得的信息
    public class Info {
        public int max;
        public int min;
        public boolean isBST;

        public Info() {
            this.max = Integer.MAX_VALUE;
            this.min = Integer.MIN_VALUE;
            this.isBST = true;
        }

        public Info(int max, int min, boolean isBST) {
            this.max = max;
            this.min = min;
            this.isBST = isBST;
        }
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return bool布尔型
     */
    public boolean isValidBST (TreeNode root) {
        // write code here

        // 1.我要干什么：
        //        我要确定以root为根结点的子树是否是二叉搜索树

        // 2.我需要什么信息：
        //      获知【左子树】的【最大节点值】以及【是否二叉搜索树】
        //      获知【右子树】的【最小节点值】以及【是否二叉搜索树】
        //      综上所述，我需要左右子树的【最大和最小节点值】与【是否二叉搜索树】

        // 3.我如何利用两个子树的信息加工出来我的信息：
        //      若两棵子树均是二叉搜索树，且右 > root > 左，则true

        return process(root).isBST;
    }

    public Info process (TreeNode root) {
        // 递归出口
        if (root == null) {
            return new Info();
        }

        Info leftInfo = process(root.left);
        Info rightInfo = process(root.right);

        // 计算左右子树的真实最大值和最小值（如果为空，则置为root的值）
        int trueLeftMax = leftInfo.max != Integer.MAX_VALUE ? leftInfo.max : root.val;
        int trueLeftMin = leftInfo.min != Integer.MIN_VALUE ? leftInfo.min : root.val;
        int trueRightMax = rightInfo.max != Integer.MAX_VALUE ? rightInfo.max : root.val;
        int trueRightMin = rightInfo.min != Integer.MIN_VALUE ? rightInfo.min : root.val;
        // 计算本子树的最大值和最小值
        int myMax = Math.max(root.val, Math.max(trueLeftMax, trueRightMax));
        int myMin = Math.min(root.val, Math.min(trueLeftMin, trueRightMin));

        if (leftInfo.isBST == false || rightInfo.isBST == false) {
            // 两棵子树只要有一个不是二叉搜索树，直接false
            return new Info(myMax, myMin, false);
        }
        // 两棵子树都是二叉搜索树
        // 注意！这里的等号是为了让子节点为null时（即左右最大或最小结点的值与本结点值相同）通过判断
        if (trueLeftMax <= root.val && root.val <= trueRightMin) {
            // 且满足右min > root > 左max，则true
            return new Info(myMax, myMin, true);
        }
        return new Info(myMax, myMin, false);
    }
}