P55 - 构造完全平衡二叉树

2026-09-07 00:00    #Haskell   #99题   #二叉树  

P55 - 构造完全平衡二叉树

Construct completely balanced binary trees

官方模块：Problems.P55　核心函数：completelyBalancedTrees

← P54 二叉树定义 | P56 对称二叉树 →

题目描述

完全平衡二叉树要求每个节点的左右子树节点数之差不超过 1。给定总节点数，生成所有可能形状。

函数签名

1completelyBalancedTrees :: Int -> [Tree ()]

实现

方法一：列表推导 + 递归

 1completelyBalancedTrees :: Int -> [Tree ()]
 2completelyBalancedTrees 0 = [Empty]
 3completelyBalancedTrees n
 4  | n < 0     = []
 5  | leftSize == rightSize = combine leftSize rightSize
 6  | otherwise = combine leftSize rightSize ++ combine rightSize leftSize
 7  where
 8    leftSize  = (n - 1) `div` 2
 9    rightSize = n - 1 - leftSize
10    combine a b =
11      [Branch () l r | l <- completelyBalancedTrees a
12                     , r <- completelyBalancedTrees b]

根占一个节点，剩余 n−1n-1 个节点尽量均分。n−1n-1 为偶数时两边相同；奇数时左右可以交换。

方法二：do 记法

 1completelyBalancedTrees :: Int -> [Tree ()]
 2completelyBalancedTrees 0 = [Empty]
 3completelyBalancedTrees n
 4  | n < 0     = []
 5  | otherwise = do
 6      (leftSize, rightSize) <- splits
 7      left <- completelyBalancedTrees leftSize
 8      right <- completelyBalancedTrees rightSize
 9      pure (Branch () left right)
10  where
11    a = (n - 1) `div` 2
12    b = n - 1 - a
13    splits
14      | a == b    = [(a, b)]
15      | otherwise = [(a, b), (b, a)]

列表 monad 的 do 记法依次枚举左右子树大小和所有子树组合。与方法一相比，分支选择和树组合被写成一条回溯流程。

方法三：惰性动态规划表

如果会重复查询多个节点数，可以用惰性列表缓存每个规模的结果：

 1completelyBalancedTrees :: Int -> [Tree ()]
 2completelyBalancedTrees n
 3  | n < 0     = []
 4  | otherwise = table !! n
 5  where
 6    table = map balanced [0..]
 7
 8    balanced 0 = [Empty]
 9    balanced size
10      | a == b    = combine a b
11      | otherwise = combine a b ++ combine b a
12      where
13        a = (size - 1) `div` 2
14        b = size - 1 - a
15
16    combine a b =
17      [Branch () left right | left <- table !! a, right <- table !! b]

table !! n 只在需要时计算，并复用规模更小的结果，不需要额外的 memoization 包。

方法对比

方法特点
列表推导递归关系最直接，推荐
列表 monad把所有选择写成回溯流程
惰性动态规划表复用不同规模的子问题结果

测试

1>>> length (completelyBalancedTrees 4)
24
3>>> completelyBalancedTrees 0
4[Empty]
5>>> all ((== 4) . treeSize) (completelyBalancedTrees 4)
6True

参考