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