c++ - 二叉树中的递归函数解释

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 of right 怎么算？或根->右->左->左？？ 谢谢

Answer 1

对于递归函数，你应该递归思考!以下是我对这个功能的看法:

• 我开始写函数的签名，也就是

  int countNodes( TreeNode *root ) 
  

• 首先，非递归的情况。例如，如果给定的树是 NULL，则没有节点，所以我返回 0。

• 然后，我观察到我树中的节点数是左子树的节点数加上右子树的节点数加1(根节点)。因此，我基本上为左右节点调用该函数，并将值也加 1。
  • 请注意，我假设该功能已经正常运行!

我为什么要这样做？很简单，该函数应该适用于任何二叉树，对吧？好吧，根节点的左子树，实际上是一棵二叉树!右子树也是二叉树。因此，我可以安全地假设使用相同的 countNodes 函数我可以计算这些树的节点数。一旦我有了它们，我只需添加 left+right+1 就可以得到我的结果。

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

假设您用这棵树调用函数:

  a
 / \
b   c
   / \
  d   e

你看到根不为空，所以你调用左子树的函数:

b

然后是右子树

   c
  / \
 d   e

虽然在调用右子树之前，需要评估左子树。

因此，您正在使用输入调用函数:

b

你看到根不为空，所以你调用左子树的函数:

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。

因此，正如您所见，对于每个左侧和右侧，您再次调用该函数，如果它们有左 child 或右 child ，该函数将被一次又一次地调用，并且每次都会在树中更深的地方调用。因此，root->left->left 或 root->right->left->left 不是直接求值，而是在后续调用之后求值。