力扣 LeetCode 98. 验证二叉搜索树（Day9：二叉树）

解题思路：

方法一：直接中序遍历放入数组（非常直观的想法）

需要注意用for循环进行重复值的判断，二叉搜索树不能有值相等的节点

class Solution {
    List<Integer> list = new ArrayList<>();

    public boolean isValidBST(TreeNode root) {
        recur(root);
        List<Integer> res = new ArrayList<>(list);
        Collections.sort(list);
        for (int i = 1; i < list.size(); i++) {
            if (list.get(i - 1).equals(list.get(i))) return false;
        }
        if (list.equals(res)) return true;
        return false;
    }

    public void recur(TreeNode root) {
        if (root == null) return;
        recur(root.left);
        list.add(root.val);
        recur(root.right);
    }
}

方法二：引入额外的一个变量进行比较（个人觉得比方法三更好理解）

class Solution {
    long pre = Long.MIN_VALUE;

    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;

        boolean isLeft = isValidBST(root.left);
        
        if (pre < root.val) pre = root.val;
        else return false;

        boolean isRight = isValidBST(root.right);

        return isLeft && isRight;
    }
}

方法三：与前一个节点进行比较

class Solution {
    TreeNode pre = null;

    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;

        boolean isLeft = isValidBST(root.left);

        if (pre != null && pre.val >= root.val) return false;
        pre = root;

        boolean isRight = isValidBST(root.right);

        return isLeft && isRight;
    }
}

原文地址：https://blog.csdn.net/qq_61504864/article/details/143944176

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！