验证二叉树只有35%通过率？搞它

热心的大肚皮

发布于 2023-02-28 13:56:33

1810

发布于 2023-02-28 13:56:33

文章被收录于专栏：程序猿日常笔记

大家好，我是热心的大肚皮，皮哥。无意间看到了，力扣上验证二叉搜索树只有35%的通过率，我们就搞专门这种，看看为什么会这么低呢？

看看它的真面目

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

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

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

提示：

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

盘它

题目信息非常简单，一个二叉树，边界值大家应该不陌生，int的边界值。上篇提到过，递归是处理二叉树的一把利刃。思路有了，不多说，上代码盘它。

round 1

public boolean isValidBST(TreeNode root) {
    return isValid(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
// 采用递归的思路，每一个节点都去比较是否符合要求
private boolean isValid(TreeNode root, int minVal, int maxVal) {
    if (root == null) {
        return true;
    }
    // 二叉树的节点值规则  
    // 左节点 小于上一个节点的值，
    // 右节点 大于上一个节点的值
    if (root.val > minVal && root.val < maxVal) {
        return isValid(root.left, minVal, root.val) 
                  && isValid(root.right, root.val, maxVal);
    } else {
        return false;
    }
}

提交之后，果断成了炮灰，仔细一看原因是-231 <= Node.val <= 231 - 1,原来边界没有处理好,那怎么解决呢，大家不用想了，如果用条件判断边界值，代码会极其冗余，那么int装不下边界，那我换成long呢？

round 2

public boolean isValidBST(TreeNode root) {
    return isValid(root, Long.MIN_VALUE, Long.MAX_VALUE);
}

private boolean isValid(TreeNode root, long minVal, long maxVal) {
    if (root == null) {
        return true;
    }
    if (root.val > minVal && root.val < maxVal) {
        return isValid(root.left, minVal, root.val) && isValid(root.right, root.val, maxVal);
    } else {
        return false;
    }
}

提交之后，果断成功。

总结

给大家个建议，在操作二叉树的时候，可以拆解成每一个节点该如何操作，利用递归的思想。最后留一个思考题，我们递归可以搞定它，那么还有其他的方式吗，前中后三种遍历哪种适合呢？

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-12-24，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树