haskell - haskell 检查平衡树

Question

如何检查这棵树是否平衡？

data Tree a = Leaf a | Node (Tree a) (Tree a)

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

这是我到目前为止所拥有的：

isBalancedTree :: Tree a -> Bool
isBalancedTree (Node l r) = abs (size l - size r) <= 1
                            && isBalancedTree l && isBalancedTree r
isBalancedTree _ = False

Answer 1

叶子是平衡的，所以最后一行应该真正评估为True，这会导致您：

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