K12教育赛事综合服务平台
聚乐之家官方网站
下载聚乐之家官方App
专注青少年竞赛题库网站
二叉搜索树的定义为:左子树的所有节点值均小于当前节点值,右子树的所有节点值均大于当前节点值,且左右子树也均为二叉搜索树。
递归过程中为每个节点维护允许的取值范围(下界low和上界high),判断当前节点值在(low, high)区间内,再递归验证左子树的上界为当前节点值、右子树的下界为当前节点值,左右子树都验证通过则为合法BST
仅需要判断当前节点值大于左孩子节点值、小于右孩子节点值,再递归验证左右子树均满足该规则即可
递归时仅需要将当前节点值作为左子树的上界(无需维护下界),将当前节点值作为右子树的下界(无需维护上界)即可
递归验证的终止条件为当前节点无左右孩子时直接返回false