haskell - Haskll，高度平衡检查

Question

有没有办法转换它，以便它根据高度检查平衡？（假设这就是问题所在。）

size :: Tree a -> Int
size (Leaf n)    = 1
size (Node x z) = size x + size z + 1

isBalanced :: Tree a -> Bool
isBalanced (Leaf _) = True
isBalanced (Node l r) = 
    let diff = abs (size l - size r) in
    diff <= 1 && isBalanced l && isBalanced r

例如：

isBalanced (Node (Node (Leaf 1)(Leaf 3)) (Leaf 2)) )  = True (Currently returns False)
isBalanced (Node (Node (Leaf 1)(Node (Leaf 1)(Leaf 3))) (Leaf 2))) = False

Answer 1

似乎size计算了节点的总数。如果你想计算（最大）高度，你需要这样的东西：

height :: Tree x -> Int
height (Leaf _) = 1
height (Node x y) = 1 + (height x `max` height y)

如果你只是用 替换size，height代码isBalanced应该像以前一样工作。

当然，这是否能解决你的问题还有待观察......