关于验证逻辑的问题

来源:11-4 验证二叉搜索树-代码实操

Nick_arron

2019-08-06

  1. 老师讲的内容主要是给定数组,如何构建一个二叉搜索树。
  2. 对于给定一个二叉树,验证是否是二叉搜索树的逻辑,存在两个问题:
    • 没有考虑等于的情况,等于也不符合二叉搜索树的条件
    • 验证的过程,当前节点只与自己的子节点进行了比较,但是并没有和整个子树进行比较。比如下面的示例,每个节点自身都符合条件,但是右面子树7 < 10,并不符合二叉搜索树的条件。
         10
       5     15
     1  6  7   20
    
  3. 参考leetcode的一种解法,每一个节点不应该只和子节点作比较,而应该和整个子树的界限进行比较,lower和upper作为比较的界限,初始值分别为 -Infinity+Infinity,在比较的过程中,如果前一次比较符合条件,即lower < val <upper,此时val应该作为node.leftuppernode.rightlower,然后继续递归比较,代码如下:
    function isValidBST (root) {
      let walk = (node, lower = -Infinity, upper = Infinity) => {
        if (!node) return true
        let val = node.val
        if (val <= lower || val >= upper) {
          return false
        }
        if (!walk(node.right, val, upper)) { 
          return false
        }
        if (!walk(node.left, lower, val)) {
          return false
        }
        return true
      }
      return walk(root)
    }
    
    
  4. 简化后两步的比较过程
    function isValidBST(root) {
      let walk = (node, lower = -Infinity, upper = Infinity) => {
        if (!node) return true
        let val = node.val
        if (val <= lower || val >= upper) {
          return false
        }
        return walk(node.right, val, upper) && walk(node.left, lower, val)
      }
      return walk(root)
    };
    
写回答

1回答

快乐动起来呀

2019-08-12

感谢同学的反馈,这块确实是有问题,也有几个同学反馈,我稍后优化下,如果能把代码贡献到 git.imooc.com 的issue就更好了

0
0

JavaScript版 数据结构与算法

填补前端同学的算法短板,掌握面试中最常见的算法与数据结构

2467 学习 · 395 问题

查看课程