关于BST递归的困惑

Question

当您可以调用递归方法而不是必须将递归方法设置为变量时，是否有一种简单的方法来理解？

例如...
只是调用递归函数遍历：
self.recurse（node.left）
self.recurse（node.right）

必须将递归函数设置为node。左和右。右：
节点。左=自我。递归（node.left）
节点。右=自我。递归（node.left）

另一个例子是删除bst中的一个节点，你必须将递归函数设置为root.left和root.right....我明白了，但不完全明白...有没有一个简单的方法来理解什么时候你可以调用递归函数，而不是必须将其设置为node.left、node.right.等...？

def deleteNode(self, root: TreeNode, key:int) -> TreeNode:
    
    if not root:
        return root
    if key < root.val:
        root.left = self.deleteNode(root.left,key)
    elif key > root.val:
        root.right = self.deleteNode(root.right,key)
    else:
        if not root.left:
            return root.right
        elif not root.right:
            return root.left
        
        root.val = self.successor(root.right)
        root.right = self.deleteNode(root.right,root.val)
    
    return root

Answer 1

要理解上述两种情况（简单递归调用和设置html" target="_blank">变量递归调用的结果），请尝试理解以下代码/函数。

比如说，你有一棵树，它在每个节点中包含一个值，其中的值要么是负值，要么是正值。现在让我们假设，你要计算有多少节点的值是正的。此问题的树结构如下所示：

TREE{
  Integer val;
  TREE left = right = null;
}

现在你让我来解决这个问题。我写了一个函数/方法，它可以用正值计算节点数。功能如下：

Integer countNodes(TREE node){
  if(node == null){
     return 0;
  }else{
      Integer count = 0; // which will count how many nodes are there with positive value
      if(node.val >= 0){
         count += 1; // if the value is positive I incremented count
      }

      // and we are checking every other nodes present in the TREE
      getCount(node.left);
      getCount(node.right);

     // and return the final result
     return count;
  }
}

现在我把我的函数还给你，你执行了！但是什么！这是大错特错！它一次又一次地给出错误的结果！！

但是为什么？？？

让我们来分析一下。

 if(node.val >= 0){
     count += 1;
 }

在那之前我们是对的！但问题是，我们增加了计数，但没有使用它！每次我们递归调用函数时，都会创建一个新的堆栈框架，创建一个名为“count”的新变量，但我们没有使用这个值！

要使用变量“count”，我们需要重新初始化对变量的每次递归调用的返回值，这样我们可以在当前堆栈帧和上一个堆栈帧以及上一个堆栈帧的上一个之间保持链接，然后继续！。。我们需要对函数countNodes进行一些更改，如下所示：

  if(node.val >= 0){
      count += 1;
  }

  count += getCount(node.left);  // re-initialize count in each recursive call
  count += getCount(node.right); // re-initialize count in each recursive call

  return count;

现在一切都会好起来的！这个代码会完美工作的！

以上场景暗示了你的问题。

self.recurse（node.left）

自己递归（node.right）

这只不过是简单地遍历所有节点。

但如果需要使用每个递归的返回结果，则需要将返回值初始化/重新初始化为变量。这就是发生在：

节点。左=自我。递归（node.left）

节点。右=自我。递归（node.left）

我希望这个长（有点长）的解释将有助于进一步。快乐编码！：）