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

import java.util.Stack;

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

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return bool布尔型
     */
    public boolean isValidBST (TreeNode root) {
        // write code here
        if (null == root.left && null == root.right) { // 只有一个根节点，当然是二叉搜索树啦
            return true;
        }
        // 思路：如果是二叉搜索树，那么使用中序遍历这棵树，就能得到一个递增的序列
        // 定义一个栈
        Stack<TreeNode> st = new Stack<>();
        // 定义一个整型变量，用于存放临时数据
        int val = Integer.MIN_VALUE;
        // 定义一个辅助节点
        TreeNode tmp = root;
        // 初始化
        while (null != tmp) { // 将这棵树的最左边的节点全部压到栈里去
            st.push(tmp);
            tmp = tmp.left;
        }
        while (!st.isEmpty()) { // 栈不为空
            tmp = st.pop();
            if (tmp.val > val) { // 如果新弹出的节点的值比它前一个弹出节点的值大，那么更新 val
                val = tmp.val;
            }
            else { // 否则，这就不是一棵二叉搜索树，直接返回 false 即可
                return false;
            }
            if (null != tmp.right) { // 如果以这个节点为根节点的树有右子树，那么就将右子树的最左边的节点全部压到栈里去
                tmp = tmp.right;
                while (null != tmp) {
                    st.push(tmp);
                    tmp = tmp.left;
                }
            }
        }
        return true;
    }
}