P62 - 收集二叉树指定层的节点
Collect nodes at a given level in a list
官方模块：
Problems.P62核心函数：atLevel
函数签名
1atLevel :: Tree a -> Int -> [a]
实现
方法一：递归带深度计数器
1atLevel :: Tree a -> Int -> [a]
2atLevel Empty _ = []
3atLevel _ level | level < 1 = []
4atLevel (Branch x _ _) 1 = [x]
5atLevel (Branch _ left right) level =
6 atLevel left (level - 1) ++ atLevel right (level - 1)
递归进入左右子树时层数减 1，层数为 1 时收集节点。
方法二：BFS 层序遍历
1atLevel :: Tree a -> Int -> [a]
2atLevel tree level = go [tree] level
3 where
4 go [] _ = []
5 go _ 0 = []
6 go nodes 1 = [x | Branch x _ _ <- nodes]
7 go nodes n = go (concatMap children nodes) (n - 1)
8 children Empty = []
9 children (Branch _ l r) = [l, r]
按层展开，直到目标层。适合需要多层的场景。
测试
1>>> atLevel tree1 2
2"bc"
3>>> atLevel tree1 4
4"g"
5>>> atLevel tree1 5
6[]