leetcode98验证二叉搜索树-递归法解-反正就是中序遍历的变式-日记篇

声明：问题描述来源于leetcode

一、问题描述：

98. 验证二叉搜索树

难度中等1808

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

• 节点的左子树只包含 小于 当前节点的数。
• 节点的右子树只包含 大于 当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

示例 1：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-3NQl2EgO-1667982398330)(https://assets.leetcode.com/uploads/2020/12/01/tree1.jpg)]

输入：root = [2,1,3]
输出：true
1
2

示例 2：

输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。
1
2
3

提示：

• 树中节点数目范围在[1, 104] 内
• -231 <= Node.val <= 231 - 1

二、题解：

分析：如果单独来判断每一个节点的话，那么就是说要名字node.left.val

start

class Solution {
    boolean result = true;

    public boolean isValidBST(TreeNode root) {
        search(root);
        return result;
    }

    private void search(TreeNode root) {
        if (!result || root == null) return;
        if (root.left != null){
            if (root.left.val >= root.val){
                result = false;
                return;
            }
        }
        if (root.right != null){
            if (root.right.val <= root.val){
                result = false;
                return;
            }
        }
        search(root.left);
        search(root.right);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

可惜，结果不行，比如说下面这个情况：

细细看每一个节点应该都是符合的，但是放在整体里，val为3的节点比根节点小，因此不符合，所以说这个是在整体上也符合二叉搜索树的。因此该题应该是如果该树的中序遍历出的链表元素如果不是单调递增，那么就是false了。

于是我们可以将结果进行中序遍历，再判断该链表是否为单调递增的。即可

那么没有剪枝的话应该是这样：

public class Solution {
    List<Integer> list = new LinkedList<>();
    public boolean isValidBST(TreeNode root) {
        search(root);
        return compare();
    }

    private boolean compare() {
        int before = list.get(0);
        for (int i = 1; i < list.size(); i++) {
            if (before >= list.get(i)) return false;
            before = list.get(i);
        }
        return true;
    }

    private void search(TreeNode root) {
        if (root.left != null) search(root.left);
        list.add(root.val);
        if (root.right != null) search(root.right);
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

end

可以这样剪枝，直接在添加链表元素进行判断：

class Solution {
    List<Integer> list = new LinkedList<>();
    boolean result = true;

    public boolean isValidBST(TreeNode root) {
        search(root);
        if (list.size() >= 2 &&
                list.get(list.size() - 1) <= list.get(list.size() - 2)) {
            result = false;
        }
        return result;
    }

    private void search(TreeNode root) {
        if (!result) return;
        if (list.size() >= 2 &&
                list.get(list.size() - 1) <= list.get(list.size() - 2)) {
            result = false;
            return;
        }
        if (root.left != null) search(root.left);
        if (list.size() >= 2 &&
                list.get(list.size() - 1) <= list.get(list.size() - 2)) {
            result = false;
            return;
        }
        list.add(root.val);
        if (root.right != null) search(root.right);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

end

虽然剪枝了，但是可能是链表操作可能比较繁琐,空间又浪费很多，因为仅仅是比较链表最后两个元素，前面的元素再前面进行比较过后就已经没有用了。思考一下，这些不就是要对前一个元素和后一个元素作比较嘛。比较的时机是即将要添加下一个元素的时候，那么我们可使用一个变量before记录前一个元素，当对下一个元素进行比较时就拿出before来进行比较，如果前一个元素较小，before=后一个元素；如果before >= 后一个元素，那么就可以知道这个二叉树不是二叉搜索树了。直接换成基本数据类型来校对那就空间和时间的消耗就很小了。

public class Solution {
    long before = Long.MIN_VALUE;
    boolean result = true;

    public boolean isValidBST(TreeNode root) {
        search(root);
        return result;
    }

    private void search(TreeNode root) {
        if (!result) return;
        if (root.left != null) search(root.left);
        if (before >= root.val) {
            result = false;
            return;
        } else {
            before = root.val;
        }

        if (root.right != null) search(root.right);

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23