P58 - 对称且完全平衡的二叉树
Symmetric and completely balanced binary trees
官方模块：
Problems.P58核心函数：symmetricBalancedTrees
题目描述
找出同时满足"完全平衡"和"对称"的二叉树。即 P55 和 P56 的组合。
函数签名
1symmetricBalancedTrees :: Int -> [Tree ()]
实现
方法一：筛选法
1symmetricBalancedTrees :: Int -> [Tree ()]
2symmetricBalancedTrees = filter symmetric . completelyBalancedTrees
P55 已生成所有完全平衡树，P56 已能判断对称性。这道题就是两个性质的组合。
方法二：直接构造对称树
1symmetricBalancedTrees :: Int -> [Tree ()]
2symmetricBalancedTrees 0 = [Empty]
3symmetricBalancedTrees n
4 | n < 0 = []
5 | otherwise = concat [mkSymmetric a b | a <- [0..n-1], let b = n - 1 - a, abs (a - b) <= 1]
6 where
7 mkSymmetric a b = [Branch () l r | l <- trees a, r <- trees b, mirror l r]
8 trees = completelyBalancedTrees
在构造阶段就要求左右子树互为镜像，比先全部生成再过滤更早剪枝。
测试
1>>> length (symmetricBalancedTrees 5)
22
3>>> all symmetric (symmetricBalancedTrees 7)
4True
5>>> all ((== True) . symmetric) (symmetricBalancedTrees 9)
6True