You need to enable JavaScript to run this app. Haskell满二叉树判断函数fullA测试结果异常问题求助
优惠活动
大模型
产品
解决方案
定价
更多

Haskell满二叉树判断函数fullA测试结果异常问题求助

满二叉树判断函数的异常成因

核心问题定位

你当前实现对单分支节点One的判断逻辑存在本质偏差,这也是测试用例输出异常的根本原因。
首先对齐满二叉树的判定标准:所有非叶子节点必须恰好拥有两个子节点,整棵树中不存在任何单分支结构的节点。

错误执行流复现

针对测试用例fullA (One 0 (One 1 (Leaf 2))),按照你编写的函数逻辑逐层递归计算的过程如下:

  • 最内层Leaf 2匹配叶子分支规则,返回True
  • 中间层One 1 (Leaf 2)匹配单分支规则,执行not (fullA (Leaf 2)),得到结果False
  • 最外层One 0 (One 1 (Leaf 2))再次匹配单分支规则,执行not (fullA (One 1 (Leaf 2)))——也就是对中间层的结果再做一次取反,最终得到not False = True
    两次连续的单分支判断形成了“负负得正”的取反抵消效果,直接输出了不符合预期的True结果。

逻辑偏差根源

原函数对One单分支节点的判断写为not (fullA b),本质是把“单分支节点是否合规”和“子树是否合规”做了反向绑定:只要子树不是满二叉树,当前单分支节点就算合规。这套逻辑完全不匹配满二叉树的判定规则——实际上只要当前节点是单分支结构,无论子树是什么形态,整棵树都不可能是满二叉树,根本不需要递归判断子树的状态。

修正方案

仅需调整单分支节点的判断规则,去掉不必要的取反递归即可:

fullA :: AltTree a -> Bool
-- 叶子节点天然满足满二叉树要求
fullA (Leaf a) = True
-- 单分支节点直接判定为不符合,无需递归子树
fullA (One a b) = False
-- 双分支节点需两个子树同时满足满二叉树要求
fullA (Two a b c) = fullA b && fullA c

调整后再运行原测试用例,最外层匹配One构造子会直接返回False,和预期结果完全一致。

内容的提问来源于stack exchange,提问作者Jackson Zhu

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.10.22 11:06:04