递归计数二叉树中的叶子

Question

我不明白，为什么我不能想出一个简单的递归函数来计算二叉树上的叶子数。我很惭愧地说，我只是一片空白，盯着显示器试图弄清楚为什么一切都不起作用。为什么很难意识到什么有效，什么无效？这应该是直观的还是不直观的？

def num_leaves(tree):
    if (tree.get_left() is None) and (tree.get_right is None()):
         return 1

    #something goes here..


    return #something here..

有人可以提供一些建议，为什么我觉得这不像它想象的那么简单

谢谢

Answer 1

我怀疑这是您处理递归的头几次之一。之所以这样说，是因为前几次我也有同感。

您的想法是正确的：您已经确定并（正确）实施了您的基本案例。所以，让我们在实际编写代码之前写下关于解决方案的一些想法：

基本思路:

识别一个 BTree 的所有叶子
如果一个节点没有子节点，它就是一片叶子
如果一个节点确实有子节点，那么它就不是叶节点。统计左边BTree的叶子数和右边BTree的节点数相加

好的，现在我们有了基本的想法，让我们尝试一些伪代码:

function countLeaves(rootNode):
    if nootNode has no children:  # this is a leaf
        return 1
    if rootNode has a left child:  # non-leaf nodes may be missing a left or right child
        leftLeaves = countLeaves(left child of rootNode)
    else:
        leftLeaves = 0

    if rootNode has a right child:
        rightLeaves = countLeaves(right child of rootNode)
    else:
        rightLeaves = 0

    return leftLeaves + rightLeaves

有道理吗？好的，让我们写一些 python 代码：

def countLeaves(root):
    if (root.get_left() is None) and (root.get_right() is None):  # we are a leaf
        return 1

    leftChild = root.get_left()
    if leftChild is not None:
        leftChildren = countLeaves(leftChild)
    else:
        leftChildren = 0

    rightChild = root.get_right()
    if rightChild is not None:
        rightChildren = countLeaves(rightChild)
    else:
        rightChildren = 0

    return leftChildren + rightChildren

现在我们已经把这个想法编码了，让我们稍微整理一下：

def countLeaves(root):
    if root.get_left() is None and root.get_right() is None: return 1
    return (0 if root.get_left() is None else countLeaves(root.get_left())) + (0 if root.get_right() is None else countLeaves(root.get_right()))

递归计数二叉树中的叶子

Recursion counting leaves in binary trees

recursion

binary-tree

python-3.x