关于验证逻辑的问题
来源:11-4 验证二叉搜索树-代码实操

Nick_arron
2019-08-06
- 老师讲的内容主要是给定数组,如何构建一个二叉搜索树。
- 对于给定一个二叉树,验证是否是二叉搜索树的逻辑,存在两个问题:
- 没有考虑等于的情况,等于也不符合二叉搜索树的条件
- 验证的过程,当前节点只与自己的子节点进行了比较,但是并没有和整个子树进行比较。比如下面的示例,每个节点自身都符合条件,但是右面子树7 < 10,并不符合二叉搜索树的条件。
10 5 15 1 6 7 20
- 参考leetcode的一种解法,每一个节点不应该只和子节点作比较,而应该和整个子树的界限进行比较,lower和upper作为比较的界限,初始值分别为
-Infinity
和+Infinity
,在比较的过程中,如果前一次比较符合条件,即lower < val <upper
,此时val
应该作为node.left
的upper
,node.right
的lower
,然后继续递归比较,代码如下: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) }
- 简化后两步的比较过程
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就更好了
00
相似问题