C++二叉树节点计数：解决潜在的访问越界问题

本文分析了一段用于计算二叉树节点数量的C++代码，并指出其中可能存在的访问越界问题，同时提供了相应的解决方案。

**问题代码：**cpp// 二叉树节点定义struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode() : val(0), left(nullptr), right(nullptr) {} TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}};

class Solution {public: int put_root(TreeNode* root){ queue<TreeNode*> line; line.push(root); int num=0; while(!line.empty()){ int size=line.size(); TreeNode* tmp; num+=size; // 问题出现在这个循环的条件判断部分 for(auto i=0;i!=line.size();++i){ tmp=line.front(); line.pop(); if(tmp->left) line.push(tmp->left); if(tmp->right) line.push(tmp->right); } } return num; } int countNodes(TreeNode* root) { if(root==nullptr) return 0; return put_root(root); }};

问题分析：

上述代码中，put_root 函数使用队列 line 对二叉树进行层序遍历，并统计节点数量。然而，在 for 循环的条件判断部分，使用了 line.size() 作为循环终止条件。由于在循环体内部会执行 line.pop() 操作，导致 line 的大小发生变化，进而可能导致 i 的值越界，引发访问非法内存的问题。

解决方案：

为了解决这个问题，可以在进入循环之前将 line.size() 的值先保存到一个变量中，然后在循环条件判断中使用该变量。这样可以确保每次循环都使用相同的终止条件，避免访问越界。

**修改后的代码片段：*cpp// ...while(!line.empty()){ // 将 line.size() 的值保存到 size 变量中 int size = line.size(); TreeNode tmp; num += size; // 在循环条件中使用 size 变量 for(auto i = 0; i != size; ++i){ tmp = line.front(); line.pop(); if(tmp->left) line.push(tmp->left); if(tmp->right) line.push(tmp->right); }}// ...

通过上述修改，可以有效避免在遍历二叉树时可能出现的访问越界问题，确保代码的正确性和稳定性。