P130. 验证二叉搜索树的前序遍历序列

https://algocasts.io/episodes/D1mRZemz

有个问题请教一下,为什么数组为空的时候返回 false,数组长度为 0 则返回 true,两者有哪些区别呢。

@ding

这个其实就是边界情况的定义而已,用 true 还是 false 其实都可以。

比如说,我们可以这样定义:

  • 数组为 null,无法对应一棵树(无效数据)
  • 数组长度为 0,对应空树(null tree)
  • 空树是一棵二叉搜索树

这样的定义下,null 数组就返回 false,长度为 0 的数组就返回 true。

但我们也可以定义成:

  • 数组为 null,对应空树(null tree)
  • 数组长度为 0,对应空树(null tree)
  • 空树是一棵二叉搜索树

这样的定义下,null 数组和长度为 0 的数组就都会返回 true。

上面两种定义,如果考虑映射的唯一性,第一种定义会合理一些,因此大多数时候见到的应该也是第一种定义。但如果题目另有约定,那就按题目的要求来。所以在不同的 OJ 平台,边界情况是有可能要做适当修改才能 AC 的。

1赞