Collect the nodes at a given level in a list
题目
A node of a binary tree is at level N if the path from the root to the node has length N-1. The root node is at level 1. Write a predicate atlevel/3 to collect all nodes at a given level in a list.
% atlevel(T,L,S) :- S is the list of nodes of the binary tree T at level L
Using atlevel/3 it is easy to construct a predicate levelorder/2 which creates the level-order sequence of the nodes. However, there are more efficient ways to do that.
蒐集二叉树中指定层级的节点。
用单元测试描述为：
from python99.btree.p411 import atlevel
def test_atlevel():
E = 'E'
assert atlevel(
[E, [E, None, None], [E, None, [E, None, None]]], 2) == [E, E]
assert atlevel([E, [E, [E, [E, None, None], None], None],
[E, None, None]], 3) == [E]
解题思路
与P410类似，递归遍历二叉树，遇到符合要求的节点则返回节点。这𥚃不同的是，判断条件不仅依赖节点本身及子树，还要依赖其所处的层级。层级信息必须由外部传入。所以，递归时不仅拆分子树，还要累计层级。
举个例子，给定二叉树[E, [E, None, None], [E, None, None]]，求第二层的节点。
- 从根节点开始遍历。根的层级为1，不符合要求的层级。
- 遍历左子树，层级加一为2，符合要求，所以其节点值被返回，同时中止这一子树的遍历
- 遍历右子树，层级加一为2，符合要求，所以其节点值被返回，同时中止这一子树的遍历
代码实现：
def atlevel(t, l):
if t is None:
return []
if l == 1:
return [t[0]]
return atlevel(t[1], l-1)+atlevel(t[2], l-1)