二叉树中的递归函数解释

Question

我正在阅读二叉树教程.
而且我在使用递归函数方面略有困难.比方说,我需要计算树中的节点数

int countNodes( TreeNode *root )    
{   
       // Count the nodes in the binary tree to which  
       // root points, and return the answer.  
    if ( root == NULL )  
       return 0;  // The tree is empty.  It contains no nodes.  
    else
   {  
       int count = 1;   // Start by counting the root.  
       count += countNodes(root->left);  // Add the number of nodes   
                                        //     in the left subtree.   
       count += countNodes(root->right); // Add the number of nodes   
                                        //    in the right subtree.  
       return count;  // Return the total.  
    }  
 }   // end countNodes()

现在我的疑问是 - >如何计算root-> left-> left from right？或root-> right-> left-> left ?? 谢谢

Answer 1

使用递归函数,你应该递归思考!以下是我如何看待这个功能:

• 我开始编写函数的签名,即

  int countNodes( TreeNode *root ) 
  

• 首先,这些案例不是递归的.例如,如果给定的树是NULL,那么没有节点,所以我返回0.

• 然后,我观察到我树中的节点数是左子树的节点数加上右子树的节点数加1(根节点).因此,我基本上调用左,右节点的函数,并添加值1.
  • 请注意,我认为该功能已正常工作!

我为什么这样做？很简单,该函数应该适用于任何二叉树吗？那么,根节点的左子树,是实际上是一个二叉树!右子树也是二叉树.所以,我可以安全地假设具有相同的countNodes功能,我可以计算这些树的节点.一旦我拥有它们,我只需添加左+右+ 1即可得到我的结果.

递归函数如何真正起作用？您可以使用笔和纸来遵循算法,但简而言之,它是这样的:

假设您使用此树调用该函数:

  a
 / \
b   c
   / \
  d   e

您看到root不为null,因此您调用左子树的函数:

b

以及右边的子树

   c
  / \
 d   e

在调用正确的子树之前,需要评估左子树.

所以,你正在使用输入来调用函数:

b

您看到根不是null,因此您调用左子树的函数:

NULL

返回0,右侧子树:

NULL

也会返回0.您计算树的节点数,它是0 + 0 + 1 = 1.

现在,原始树的左子树有1个

b

并调用该函数

   c
  / \
 d   e

在这里,您再次为左子树调用该函数

d

其类似于b返回1 的情况,然后是右子树

e

它也返回1并且您将树中的节点数评估为1 + 1 + 1 = 3.

现在,返回函数的第一次调用,并将树中的节点数评估为1 + 3 + 1 = 5.

因此,您可以看到,对于每个左右,您再次调用该函数,如果它们有左或右子节点,则该函数会一次又一次地被调用,并且每次在树中更深入时.因此,root->left->left或者root->right->left->left不是直接评估,而是在后续调用之后.