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

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布尔型
     */
    // answer one 使用递归方式
    // int pre = Integer.MIN_VALUE;
    public boolean isValidBST (TreeNode root) {
    //     // write code here
    //     if (root == null)
    //         return true;

    //     if (!isValidBST(root.left))
    //         return false;

    //     if (root.val < pre)
    //         return false;

    //     pre = root.val;
        
    //     return isValidBST(root.right);
    // answer two 使用栈的方式
        if (root == null) return true;

        Stack<TreeNode> s = new Stack<TreeNode>();

        ArrayList<Integer> sort = new ArrayList<Integer>();

        TreeNode head = root;

        while(head != null || !s.isEmpty()) {

            while(head != null) {
                s.push(head);
                head = head.left;
            }

            head = s.pop();
            
            sort.add(head.val);

            head = head.right;

        }
        for (int i = 1; i < sort.size(); i++){
            if (sort.get(i - 1) > sort.get(i)){
                return false;
            }
        }
        return true;
    }
}

使用栈的方式解决：

1、定义一个栈和一个数组

2、从根节点开始，每次找到当前节点的左节点，并依次放入栈中，直到找到最左节点

3、取出栈顶元素，并将当前元素的值放入数组中，若存在右子树，则将右子树放入栈中

4、一直重复以上步骤，直到当前节点为空或栈为空，最后判断数组是否是递增数组