描述

示例1

{1,2,3}

false

如题面图1  

示例2

{2,1,3}

true

如题面图2  

PRivate List<Integer> list = new ArrayList<>();
     
public boolean isValidBST (TreeNode root) {
    if (root == null) {
        return true;
    }
    boolean left = isValidBST(root.left);
    if (list.size() > 0 && root.val <= list.get(list.size() - 1)) {
        return false;
    }
    list.add(root.val);
    boolean right = isValidBST(root.right);
    return left &amp;& right;
}
    

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布尔型
     * 迭代
     */
    public boolean isValidBST (TreeNode root) {
        // wrITe code here
        Stack<TreeNode> stack = new Stack<>();
        // 当前节点的前驱节点
        TreeNode pre = null;
        while (!stack.iSEMpty() || root != null) {
            // 1、一直走到当前树的左边界
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            //2、取出栈顶元素，即当前树的最左边界节点，让其跟前驱节点进行比较，即当前节点在中序遍历得到的序列中是前驱节点的后继节点
            TreeNode pop = stack.pop();
            if (pre != null && pre.val > pop.val) {
                return false;
            }
            // 3、将当前节点的右节点设置为根节点继续重复第一个步骤（因为根据BST的定义：当前节点的右节点的值是比当前节点的父节点的值要小的）
            root = pop.right;
            // 4、将当前节点更新为前驱节点
            pre = pop;
        }
        return true;
    }
}