c++ - 计算树中的所有节点

Question

这是我当前的代码。它工作正常，但我想不出一种方法将根节点添加到计数中，因为由于程序是递归的，它总是被添加很多次。

int countTree(tnode<T> *t)
{

int count = 0;


 if (t != NULL)
 {
     count = count + countTree(t->left);

if (t->left)
    { count++; }

  count = count + countTree(t->right);

if (t->right)
    { count++; }
}


return count;

};

Answer 1

二叉树中节点计数的通常递归是1 + count(left sub-tree) + count(right sub-tree)，其中count(null) 返回 0。

所以它会是这样的:

int count(node *root)
{
    if (!root) { return 0; }

    return 1 + count(root->left) + count(root->right);
}