二叉树中根到叶节点数字之和

"这篇资源是关于解决一个二叉树算法问题的，目标是计算从根节点到所有叶节点的数字路径之和。" 在给定的题目中，我们需要解决一个与二叉树相关的算法问题。这个问题的具体描述是，给定一棵二叉树，其中每个节点上都存储了一个0到9的数字，每条从根节点到叶节点的路径就代表了一个由这些数字组成的整数。例如，从根节点到叶节点的路径1->2->3代表数字123。任务是计算所有这样的路径所表示的数字之和。 在提供的示例1中，给定的二叉树结构如下： ``` 1 / \ 2 3 ``` 从根节点1到叶子节点2的路径表示数字12，而从根节点1到叶子节点3的路径表示数字13。所以总和为12 + 13 = 25。 在示例2中，二叉树的结构如下： ``` 4 / \ 9 0 / 5 / 1 ``` 从根节点4到叶子节点9->5的路径表示495，到9->1的路径表示491，到0的路径表示40。因此，总和为495 + 491 + 40 = 1026。 为了求解这个问题，可以采用广度优先搜索（BFS）策略。参考答案中给出的C++代码片段展示了如何实现这一方法： ```cpp class Solution { public: int sumNumbers(TreeNode* root) { if (root == nullptr) { return 0; } int sum = 0; queue<TreeNode*> nodeQueue; queue<int> numQueue; nodeQueue.push(root); numQueue.push(root->val); while (!nodeQueue.empty()) { TreeNode* node = nodeQueue.front(); int num = numQueue.front(); nodeQueue.pop(); numQueue.pop(); TreeNode* left = node->left; TreeNode* right = node->right; if (left) { nodeQueue.push(left); numQueue.push(num * 10 + left->val); } if (right) { nodeQueue.push(right); numQueue.push(num * 10 + right->val); } if (!left && !right) { // 当节点是叶节点时 sum += num; } } return sum; } }; ``` 这段代码首先初始化一个队列来保存节点和当前路径上的数字。然后进行BFS遍历。在遍历过程中，每当访问到一个节点时，将该节点的左右子节点加入队列，并更新当前数字路径。当节点为叶节点（即没有子节点）时，将当前数字路径添加到总和中。最后返回总和。 这个算法的时间复杂度为O(n)，其中n是二叉树中的节点数，因为它遍历了所有的节点。空间复杂度也是O(n)，最坏情况下队列中可能需要存储所有的节点。由于题目中提到树的深度不超过10，且节点数在[1, 1000]范围内，这个解决方案在性能上是可行的。