c++ - 二叉树numNodes

int numNodes() const {
   int size = 1;

   if (left != NULL) size += left->numNodes();
   if (right != NULL) size += right->numNodes();

   return size;
}

上面的代码是用于查找树内节点数的代码，因为它使用的是递归调用，所以我不太了解它的作用。谁能解释以上递归调用或函数的工作原理。谢谢

也可以看看:

Understanding recursion

最佳答案

理解递归的关键之一是注意到您要一遍又一遍地解决相同的问题。

最初的问题是“此树中有多少个节点？”您可以通过在左侧子树和右侧子树中添加节点来解决此问题。现在，您有两个较小的问题:计算节点在左右子树中。

这是的技巧:这两个较小的问题(计算子树中的节点)几乎与您开始时(计算所有节点)的问题相同。唯一的区别是子树比原始树小一点。

像您发布的那样，一种聪明的递归算法将利用这些问题之间的相似性，以很少的代码来解决问题。

首先，递归代码确实很难引起您的注意。构成示例树并仔细研究它，假装自己是计算机，直到您相信它为止。