P61 - 收集叶子节点与内部节点

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

P61 - 收集叶子节点与内部节点

Collect nodes of a binary tree

官方模块：Problems.P61　核心函数：leaves、internals

← P60 指定节点数的高度平衡树 | P62 收集指定层节点 →

题目描述

叶子节点没有任何子节点；内部节点至少有一个非空子树。分别按从左到右的顺序收集二者。

函数签名

1leaves :: Tree a -> [a]
2internals :: Tree a -> [a]

实现

方法一：直接递归

 1leaves :: Tree a -> [a]
 2leaves Empty                  = []
 3leaves (Branch x Empty Empty) = [x]
 4leaves (Branch _ left right)  = leaves left ++ leaves right
 5
 6internals :: Tree a -> [a]
 7internals Empty                  = []
 8internals (Branch _ Empty Empty) = []
 9internals (Branch x left right)  =
10  internals left ++ [x] ++ internals right

叶子按左右子树的顺序拼接。内部节点采用中序顺序：左子树、当前节点、右子树。

方法二：累加参数（差异列表）

 1leavesAcc :: Tree a -> [a]
 2leavesAcc tree = gather tree []
 3  where
 4    gather Empty tail = tail
 5    gather (Branch x Empty Empty) tail = x : tail
 6    gather (Branch _ left right) tail =
 7      gather left (gather right tail)
 8
 9internalsAcc :: Tree a -> [a]
10internalsAcc tree = gather tree []
11  where
12    gather Empty tail = tail
13    gather (Branch _ Empty Empty) tail = tail
14    gather (Branch x left right) tail =
15      gather left (x : gather right tail)

gather tree tail 表示“遍历结果后面继续接 tail”，因此不需要第三方 DList 包，也避免反复执行 ++。

方法对比

方法特点
直接递归与节点定义对应，最容易阅读
累加参数单次线性构造结果，适合偏斜树

测试

1>>> leaves (Branch 'a' (leaf 'b') (leaf 'c'))
2"bc"
3>>> internals (Branch 'a' (leaf 'b') (leaf 'c'))
4"a"
5>>> leavesAcc (Branch 'a' (leaf 'b') (leaf 'c')) == leaves (Branch 'a' (leaf 'b') (leaf 'c'))
6True
7>>> internalsAcc (Branch 'a' (leaf 'b') (leaf 'c')) == internals (Branch 'a' (leaf 'b') (leaf 'c'))
8True

参考