Count the leaves of a binary tree
题目
A leaf is a node with no successors. Write a predicate count_leaves/2 to count them.
% count_leaves(T,N) :- the binary tree T has N leaves
没有后继者的节点称为叶子。在我们的数据模型中，左右子节点都是空树的节点即为叶子。
单元测试描述为：
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 count_leaves(t):
if t is None:
return 0
if t[1] is None and t[2] is None:
return 1
return count_leaves(t[1]) + count_leaves(t[2])