Haskell下判断自定义Btree二叉树是否为完全二叉树的问题求解

问题原因分析 #

• 第一个错误：你当前go函数返回的第二个值是子树的节点总数，不是子树深度，用节点数相等判断左右子树高度一致的逻辑完全错误，这是ex1返回False的直接原因：ex1根节点左子树有3个节点，右子树有2个节点，触发leftCount == rightCount判断失败。
• 第二个错误：现有逻辑完全没有校验你给出的三条判定规则里的Unary节点限制（最多1个、必须在倒数第二层），也没有校验叶子深度差、最深叶子靠左的规则。

修复后的实现代码 #

我们调整go函数的返回值，每个子树返回四个参数：(是否合法, 最大深度, 最小深度, 子树内Unary节点数量)，再逐层校验规则：

complete :: Btree a -> Bool
complete x = valid && maxDepth - minDepth <= 1 && unaryCnt <= 1
  where
    (valid, maxDepth, minDepth, unaryCnt) = go x
    -- Leaf节点：合法，深度0，最小最大都是0，没有Unary
    go (Leaf _) = (True, 0, 0, 0)
    -- Unary节点处理：只能有1个，且子树必须是Leaf（保证当前Unary在倒数第二层）
    go (Unary left _) = 
      let (leftValid, leftMax, leftMin, leftUnary) = go left
          curValid = leftValid && leftMax == 0 && leftUnary == 0
      in (curValid, leftMax + 1, leftMin + 1, leftUnary + 1)
    -- Binary节点处理
    go (Binary left _ right) = 
      let (leftValid, leftMax, leftMin, leftUnary) = go left
          (rightValid, rightMax, rightMin, rightUnary) = go right
          -- 校验规则：左右子树合法、左深度≥右深度（保证最深叶子靠左）、深度差≤1、Unary总数≤1、左有缺口时右深度必须小1
          curValid = leftValid && rightValid 
                  && leftMax >= rightMax 
                  && leftMax - rightMax <= 1 
                  && leftUnary + rightUnary <= 1
                  && (leftUnary == 0 || rightMax == leftMax - 1)
          curMax = max leftMax rightMax + 1
          curMin = min leftMin rightMin + 1
          curUnary = leftUnary + rightUnary
      in (curValid, curMax, curMin, curUnary)

测试用例验证 #

• ex1：返回True，符合预期
• ex2：返回False（Unary节点出现在左子树，不符合最深叶子靠左要求）
• ex3：返回True，符合预期

内容的提问来源于stack exchange，提问作者user16506618