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

思路:
1.二叉搜索树，左边的节点比根小，右边的节点比根大。中序遍历的结果是从小到大排序的
2.递归，树的中序遍历，拿到中间节点后，比较是否当前的数比前面的数小，小就不是二叉搜索树
3.看之前的中序遍历TOP24,我们还可以用栈的做法实现。

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 {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return bool布尔型
     */
    int pre = Integer.MIN_VALUE;
    public boolean isValidBST (TreeNode root) {
        // write code here
        //方法二
        return isValidBFS(root);
        //方法一
//         if (root == null) {
//             return true;
//         }
//         //左
//         if (!isValidBST(root.left)) {
//             return false;
//         }
//         //根
//         if (root.val < pre) {
//             return false;
//         }
//         pre = root.val;
//         //右
//         if (!isValidBST(root.right)) {
//             return false;
//         }
//         return true;
    }

    private boolean isValidBFS(TreeNode node) {
        if (node == null) {
            return true;
        }
        //假设根的值最小，左子树最左一个节点开始
        int pre = Integer.MIN_VALUE;

        Stack<TreeNode> stack = new Stack<>();
        TreeNode currentNode = node;
        while (currentNode != null || !stack.empty()) {

            while (currentNode != null) {
                stack.push(currentNode);
                currentNode = currentNode.left;
            }
            currentNode = stack.pop();
            //最后一个左节点
            if (currentNode.val < pre) {
                return false;
            }
            pre = currentNode.val;
            //左节点的右节点
            currentNode = currentNode.right;

        }
        return true;

    }
}