P59 - 构造高度平衡二叉树

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

P59 - 构造高度平衡二叉树

Construct height-balanced binary trees

官方模块：Problems.P59　核心函数：heightBalancedTrees

← P58 对称平衡树 | P60 指定节点数的高度平衡树 →

题目描述

高度平衡要求每个节点的左右子树高度差不超过 1。给定高度 hh，生成所有恰好为该高度的树形。

函数签名

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

实现

方法一：组合高度（标准解）

 1heightBalancedTrees :: Int -> [Tree ()]
 2heightBalancedTrees 0 = [Empty]
 3heightBalancedTrees 1 = [leaf ()]
 4heightBalancedTrees h
 5  | h < 0     = []
 6  | otherwise =
 7      combine tall tall ++ combine tall short ++ combine short tall
 8  where
 9    tall  = heightBalancedTrees (h - 1)
10    short = heightBalancedTrees (h - 2)
11    combine ls rs = [Branch () l r | l <- ls, r <- rs]

要让根的高度为 hh，至少一侧必须高 h−1h-1；另一侧只能是 h−1h-1 或 h−2h-2，所以恰好有三种高度组合。

方法二：惰性动态规划表

 1heightBalancedTrees :: Int -> [Tree ()]
 2heightBalancedTrees h
 3  | h < 0     = []
 4  | otherwise = table !! h
 5  where
 6    table = [ [Empty], [leaf ()] ] ++ map build [2..]
 7
 8    build height =
 9      combine tall tall ++ combine tall short ++ combine short tall
10      where
11        tall = table !! (height - 1)
12        short = table !! (height - 2)
13
14    combine leftTrees rightTrees =
15      [Branch () left right | left <- leftTrees, right <- rightTrees]

惰性列表保存每个高度的全部结果。高度 hh 只引用已经定义的 h−1h-1 和 h−2h-2 项，因此多个高度查询可以复用子问题，而不是重新递归生成。

辅助推导：给定高度求最小节点数

1minNodes :: Int -> Int
2minNodes 0 = 0
3minNodes 1 = 1
4minNodes h = 1 + minNodes (h - 1) + minNodes (h - 2)

辅助函数：高度为 h 的高度平衡树至少有 MhM_h 个节点，Mh=1+Mh−1+Mh−2M_h = 1 + M_{h-1} + M_{h-2}（类斐波那契）。

测试

1>>> length (heightBalancedTrees 3)
215
3>>> all ((== 3) . treeHeight) (heightBalancedTrees 3)
4True
5>>> heightBalancedTrees 0
6[Empty]

参考