时间戳

首页 > 解决方案 > 关于 BST 递归的困惑

recursion - 关于 BST 递归的困惑

问题描述

有没有一种简单的方法可以理解何时可以调用递归方法而不是必须将该递归方法设置为变量？

比如……
只要调用递归函数遍历即可：
self.recurse(node.left)
self.recurse(node.right)

必须将递归函数设置为 node.left 和 node.right：
node.left = self.recurse(node.left)
node.right = self.recurse(node.left)

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

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

标签： recursiontreebinary-treebinary-search-tree

解决方案

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

假设您有一个树，它在每个节点中都包含一个值，其中值是负数或正数。现在让我们说，你要计算有多少节点的值为正。这个问题的树结构如下：

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)

self.recurse(node.right)

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

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

node.left = self.recurse(node.left)

node.right = self.recurse(node.left)

我希望这个长（有点长）的解释将有助于走得更远。快乐编码！:)

推荐阅读