查找大小递归

我已经实现了功能查找使用递归二叉树的大小（引用书上的数据结构和算法）查找大小递归

的代码片段看起来像：

// Returns the total number of nodes in this binary tree (include the root in the count). 
public static int size(BinaryTreeNode root) { 
    int leftCount = root.left == null ? 0 : size(root.left); 
    int rightCount = root.right == null ? 0 : size(root.right); 
    return 1 + leftCount + rightCount; 
}

它也可以工作。但是我无法理解递归函数调用之间leftCount和rightCount元素如何递增？它不应该像下面这样做：

// Returns the total number of nodes in this binary tree (include the root in the count). 
public static int size(BinaryTreeNode root) { 
    int leftCount = 0; 
    int rightCount = 0; 
    leftCount = leftCount + (root.left == null ? 0 : size(root.left)); 
    rightCount = rightCount+ (root.right == null ? 0 : size(root.right)); 
    return 1 + leftCount + rightCount; 
}

为下面的二叉树的某些原因两者的功能得到相同的结果（7，这是正确的）。

来源

2015-08-15 Ayusman

你的第二个版本与第一个版本完全相同 - 你不会神奇地多次调用'size（root.left）'（和right） - 你只需要调用它一次，但是当你调用相同的函数时在再次它被称为递归 - 只是想象你正在调用这个函数的新实例（与其他参数等）...所以当你最终称它为第二，第三，...时间'根'，当然' root.left'已经改变了，'leftCount'将会是一个新变量（顺便说一下：这会让堆栈更大，树更大） – Carsten

Carsten，正如我的问题所述，我明白它的递归调用。我的问题是为什么选项1有效。如果递归调用像内存中的不同方法调用一样，返回值如何被添加？ – Ayusman

没有冒犯的意思，但我认为你实际上并没有明白它是如何工作的 - *返回值*得到**返回**并且你在最后一行中加上它们 – Carsten

原始代码看起来是正确的，并返回正确的答案。您的可选代码更加冗长 - 它的功能完全相同。记住leftCount和rightCount是每个递归调用的单独变量。

我唯一的建议是将传递给size（）函数的参数的名称从根改为node。这就清楚地表明，相同的函数可以在根节点以外的节点上运行，并且递归变得更容易理解。

来源

2015-08-15 08:57:56 kiwiron

查找大小递归

回答

相关问题