P60 - 给定节点数的高度平衡二叉树

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

P60 - 给定节点数的高度平衡二叉树

Construct height-balanced binary trees with a given number of nodes

官方模块：Problems.P60　核心函数：heightBalancedTreesWithNodes

← P59 高度平衡二叉树 | P61 收集叶子节点 →

题目描述

给定节点数 nn，找出所有恰好有 nn 个节点的高度平衡二叉树。

函数签名

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

实现

方法一：枚举高度 + 过滤

1heightBalancedTreesWithNodes :: Int -> [Tree ()]
2heightBalancedTreesWithNodes n
3  | n < 0     = []
4  | otherwise =
5      [tree | h <- [0..n]
6            , tree <- heightBalancedTrees h
7            , treeSize tree == n]

先算出所有可能的高度 hh（不超过 nn），用 P59 生成该高度的所有树，再过滤出节点数正好为 nn 的。

方法二：用 minNodes 缩小范围

 1heightBalancedTreesWithNodes :: Int -> [Tree ()]
 2heightBalancedTreesWithNodes n
 3  | n < 0     = []
 4  | otherwise =
 5      [tree | h <- [minH..maxH]
 6            , tree <- heightBalancedTrees h
 7            , treeSize tree == n]
 8  where
 9    minH = ceiling (logBase 2 (fromIntegral (n + 1))) -- 完全二叉树对应最矮高度
10    maxH = head [h | h <- [0..], minNodes h > n] - 1   -- 高度上界

用 minNodes（P59 的辅助函数）提前确定可能的高度范围，减少不必要的枚举。

测试

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

参考