Collect the leaves of a binary tree in a list
A leaf is a node with no successors. Write a predicate leaves/2 to collect them in a list.
% leaves(T,S) :- S is the list of all leaves of the binary tree T
与P408类似，不过要收集叶子节点。
单元测试描述为：
from python99.btree.p408 import count_leaves
def test_count_leaves():
E = 'E'
assert count_leaves([E, None, None]) == 1
assert count_leaves([E, [E, None, [E, None, None]], [E, None, None]]) == 2
解题思路
递归遍历二叉树，当检测到左右子树皆为空的节点，即为叶子节点。
举个例子，给定二叉树[E, [E, None, [E, None, None]], [E, None, None]]。
- 根节点的左右子树不全为空，所以根节点不是叶子
- 左子树
[E, None, [E, None, None]]的左右子树不空，所以其不是叶子- 左子树
None是空树，空树不是叶子 - 右子树
[E, None, None]的左右子树为空，所以其是叶子
- 左子树
- 右子树
[E, None, None]的左右子树为空，所以其是叶子
- 左子树
代码实现：
def leaves(t):
if t is None:
return []
if t[1] is None and t[2] is None:
return [t[0]]
return leaves(t[1])+leaves(t[2])