力扣第九十八题-验证二叉搜索树 前言 一、思路 二、实现 三

发表于

「这是我参与11月更文挑战的第17天，活动详情查看：2021最后一次更文挑战」

前言

力扣第九十八题 验证二叉搜索树 如下所示：

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

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

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

示例 1：

1
2
ini复制代码输入： root = [2,1,3]
输出： true

示例 2：

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

一、思路

二叉搜索树必须满足如下的三个条件：

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

这一题我刚开始看到就写了一个简单的递归，仅判断当前节点的值是否大于左孩子的值，以及当前节点的值是否小于右孩子的值。很显然，这样做会失败，因为会碰到如下的情况：

image.png

虽然 3 < 6 且 7 > 6，但是因为 [6, 3, 7] 作为根节点 5 的子树，他的每个节点的值都应该大于 5，故这个树不能构成二叉搜索树。

image.png

于是我就想该怎么解决这个问题呢？

刚开始我是保存了当前节点的 父节点 的值，确保以当前节点开始的子树中的值都会 大于或小于父节点的值，直到我又碰到了下面这种情况：

最下面的叶子节点 3 虽然大于它的父节点 2 以及父节点的 3。但因为它在的子树是作为根节点 3 的左孩子，所以子树中的每个节点值都应小于 3。所以这也构不成二叉搜索树。

image.png

于是我发现当前节点是否合规与他的路径有关，总结如下：

  1. 左节点 left 的值需要小于父节点，且大于第一次向右的值
  2. 右节点 right 的值需要大于父节点，且小于第一次向左的值

这是为什么呢？

其实很简单，因为 符号具有传递性，即 a > b, b > c 可以得出 a > c

举个例子：对于下图中的 i 来说。因为 g > f, f > c，只需要 i > g 就可以满足向右的节点值会一直增大。

又因为以 c 节点开始的子树是 b 节点的左孩子，c 节点开始的子树中的值都要小于 b 节点的值。那为什么不是小于 a 节点的值呢？因为即使 i < a 且 b < a，也无法判断 i 与 b 的大小。

所以，对于右节点来说，只需要大于父节点，且小于第一次向左的值
image.png

思路有了之后，实现起来就不难了。

二、实现

实现代码

实现代码与思路中保持一致

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
31
32
33
34
java复制代码    private class Path {
        Integer val;
        Boolean isLeft;

        public Path(Integer val, Boolean isLeft) {
            this.val = val;
            this.isLeft = isLeft;
        }
    }

    public boolean isValidBST(TreeNode root) {
        return dfs(root, new LinkedList<>());
    }

    public boolean dfs(TreeNode root, Deque<Path> rootValStack) {
        if (root == null)
            return true;
        // left的值需要小于父节点，且大于第一次向右的值
        if (root.left != null && (root.val <= root.left.val || rootValStack.stream().anyMatch(n -> !n.isLeft && n.val >= root.left.val))){
            return false;
        }
        // right的值需要大于父节点，且小于第一次向左
        if (root.right != null && (root.right.val <= root.val || rootValStack.stream().anyMatch(n -> n.isLeft && n.val <= root.right.val))) {
            return false;
        }
        boolean leftFlag, rightFlag;
        rootValStack.push(new Path(root.val, true));
        leftFlag = dfs(root.left, rootValStack);
        rootValStack.pop();
        rootValStack.push(new Path(root.val, false));
        rightFlag = dfs(root.right, rootValStack);
        rootValStack.pop();
        return leftFlag && rightFlag;
    }

测试代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
java复制代码    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(3, new TreeNode(1, new TreeNode(0), new TreeNode(2)),
                new TreeNode(5, new TreeNode(4), new TreeNode(6)));
        TreeNode treeNode1 = new TreeNode(2, new TreeNode(2), new TreeNode(2));
        TreeNode treeNode2 = new TreeNode(120,
                new TreeNode(70,
                        new TreeNode(50, new TreeNode(25), new TreeNode(55)),
                        new TreeNode(100, new TreeNode(75), new TreeNode(110))),
                new TreeNode(140,
                        new TreeNode(130, new TreeNode(119), new TreeNode(55)),
                        new TreeNode(100, new TreeNode(75), new TreeNode(110)))

        );
        TreeNode treeNode3 = new TreeNode(3,
                new TreeNode(1, new TreeNode(0), new TreeNode(2, null, new TreeNode(3))),
                new TreeNode(5, new TreeNode(4), new TreeNode(6)));
        boolean flag = new Number98().isValidBST(treeNode3);
        System.out.println(flag);
    }

结果

image.png

三、总结

这一题击败率不是很理想，主要是因为对于每一个节点都要找到与父节点首个拐点的值是否满足条件。不知道你看了题解之后，有想到如何优化这个算法了吗？

提示一下：去除保存父节点的路径

感谢看到最后，非常荣幸能够帮助到你~♥

如果你觉得我写的还不错的话，不妨给我点个赞吧！如有疑问，也可评论区见~

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%