二进制树 - 算法，发现叶片的叶子数量甚至深度

Question

问题如下：

找到一种算法，该算法将指向二进制树的指针(到它的开头(，并返回均匀深度(级别(的叶子数。

在此示例中，该算法将返回2，因为我们不会在级别1中计算叶子(因为1个甚至不是(。

我想我需要递归算法。如果我传递两个参数，我会通过该函数( pointer to a tree和 level(传递，这很容易。我想知道我是否只能通过指针而没有级别来解决它。

Answer 1

考虑一个函数 f ，它递归下降到树上。您必须将三种情况分开：

1. 您当前的节点没有孩子，其深度甚至是。您返回1。
2. 您当前的节点没有孩子，其深度很奇怪。您返回0。
3. 您目前的节点有孩子。您返回这些孩子上 f 的所有递归电话的总和。

您必须自己定义 f 。

否，不可能仅使用一个参数来定义 f 。您必须记住当前节点以及实际深度。从本质上讲，递归算法的位置都不知道。您当然可以(但不建议(记住，只要您不并行 f 。

，请记住后者。

另外，您可以"覆盖" f 它只需要一个对众聚者并调用功能 f 将两个参数带有两个参数，而当前深度集为0。

Answer 2

您实际上只能使用一个周长来解决它。但是，在这种情况下，您需要两个小助手功能：

typedef struct TreeNode
{
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;
int countForOdd(TreeNode*);
int countForEven(TreeNode*);
int count(TreeNode*);
//If the TreeNode to be passed as perimeter is at an odd level, call this function
int countForOdd(TreeNode *node)
{
    if(!node) return 0;
    return countForEven(node->left)
        + countForEven(node->right);
}
    //If the TreeNode to be passed as perimeter is at an even level, call this function
int countForEven(TreeNode *node)
{
    if(!node) return 0;
    return 1 + countForOdd(node->left)
        + countForOdd(node->right);
}
//And finally, our specific function for root is:
int count(TreeNode* root)
{
    return countForOdd(root);
}