LeetCode 938 一个tricky的地方

Edsger.X 发表于 2020-4-14 06:29
BST的话，左子树的节点，都小于当前node不是吗。也是就是我DFS下一层的话，当前node是最大值

        100
        /   \
      90    110
[L, R]: [10, 20]

你的写法到90这个点时，会把区间变成[10, 100]从而把90加到最终结果里

范围区间应该是[L, R]，如果改成node.value +1就变成了[L, node.value +1]，不符合题意了

Edsger.X 发表于 2020/04/14 06:29:18
BST的话，左子树的节点，都小于当前node不是吗。也是就是我DFS下一层的话，当前node是最大值

你如果想缩小搜索范围的话，应该是Math. min(R, node.val + 1) ，因为R有可能小于node.val，这样会导致多算一些值。