二叉树节点计数：提交代码至在线判题系统结果错误求助

问题背景 #

我在解决GeeksForGeeks的《Size of Binary Tree》问题，题目要求统计给定二叉树的节点总数。示例二叉树的节点数为4：

1
     / \
   10   39
  /
 5

测试用例异常情况 #

输入：

2 // 测试用例数量
1 2 3 // 测试用例#1
10 5 9 N 1 3 6  // 测试用例#2

我的输出：

3
9

预期输出：

3
6

错误代码 #

/* Tree node structure  used in the program
 struct Node
 {
     int data;
     Node* left;
     Node* right;
}; */

/* Computes the number of nodes in a tree. */

int nodes=0;

void dfs(Node* node) {
    if (node==NULL) return;
    ++nodes;
    // cout << node->data << " ";
    dfs(node->left);
    dfs(node->right);
}

int getSize(Node* node)
{
   // Your code here
   dfs(node);
   return nodes;
}

问题根源 #

你使用了**全局变量nodes**来计数，全局变量的生命周期覆盖整个程序运行期间。第一个测试用例执行后，nodes的值变为3；第二个测试用例运行时，nodes不会自动重置为0，而是在3的基础上继续累加第二个树的6个节点，最终得到3+6=9，与预期结果不符。

修复方案 #

有两种常见的修复方式：

方式1：将计数变量改为局部变量 #

在getSize函数内初始化局部计数变量，避免全局状态污染：

void dfs(Node* node, int &count) {
    if (node == NULL) return;
    ++count;
    dfs(node->left, count);
    dfs(node->right, count);
}

int getSize(Node* node)
{
   int nodes = 0;
   dfs(node, nodes);
   return nodes;
}

方式2：让DFS递归返回节点数 #

无需额外计数变量，直接通过递归返回值累加：

int getSize(Node* node)
{
   if (node == NULL) return 0;
   return 1 + getSize(node->left) + getSize(node->right);
}

这种方式更简洁，也避免了全局/引用变量的问题。

内容的提问来源于stack exchange，提问作者notVansh