递归查找二叉树的大小

Question

我已经实现了使用递归查找二叉树大小的函数（参考了一本关于数据结构和算法的书）

代码片段如下所示：

// 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，这是正确的）。

Answer 1

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

我唯一的建议是将传递给 size() 函数的参数名称从根更改为节点。这样就清楚了同一个函数可以对根节点以外的节点进行操作，递归也变得更容易理解

Answer 2

让我尝试通过单步执行您的代码来解释它是如何工作的你展示的二叉树。

您首先使用根节点 (1) 调用 size。它的左边 child (2) 不是 null 所以你用 2 调用 size。它的左边child（4）不是null，所以你用4调用size。现在，4 的左边是 null，因此您将 leftCount 设置为 0。 4右边也是null，所以你把rightCount设为0。然后你 return 1 + 0 + 0，也就是 1，到调用函数，也就是节点为 2 的函数。因此，在使用节点 2 调用的函数中，leftCount 设置为 1。现在，我们检查 2 的右边 child，它不是 null 所以我们用右边的 child 调用 size (5)。同样，5没有左也没有右child，所以leftCount和rightCount都设置为0，函数returns 1 + 0 + 0。一旦对2returns1右边的size调用，rightCount设置为1。此时用2、returns1 + 1 + 1调用的函数就是3。所以，1returns3左边调用size，然后我们用右边调用sizechild 共 1 (3)。使用节点 3 对 size 的调用与我们在使用节点 2 的调用中看到的完全相同，所以3 的计数是 return。最后，与节点 1, returns 1 + 3 + 3 的原始调用，即 7.

如果您想要更直观的解释，我制作了一个视频（find size of binary tree 在 YouTube 上），我首先解释了在较高层次上查找尺寸的过程，然后显示代码，然后运行虽然代码 step-by-step 有一个例子（通过在每个函数调用中用变量值填充 table，所以很容易看出递归是如何展开的）。

递归查找二叉树的大小

Find size of Binary Tree recursively

recursion

binary-tree

data-structures