给你一个二叉树的根节点 root ,树中每个节点都存放有一个 09 之间的数字。
每条从根节点到叶节点的路径都代表一个数字:

例如,从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123
计算从根节点到叶节点生成的 所有数字之和

叶节点 是指没有子节点的节点。

示例 1:

求根节点到叶节点数字之和-129 - 图1

  1. Input: root = [1,2,3]
  2. Output: 25
  3. Explanation:
  4. The root-to-leaf path 1->2 represents the number 12.
  5. The root-to-leaf path 1->3 represents the number 13.
  6. Therefore, sum = 12 + 13 = 25.

示例 2:

求根节点到叶节点数字之和-129 - 图2

  1. Input: root = [4,9,0,5,1]
  2. Output: 1026
  3. Explanation:
  4. The root-to-leaf path 4->9->5 represents the number 495.
  5. The root-to-leaf path 4->9->1 represents the number 491.
  6. The root-to-leaf path 4->0 represents the number 40.
  7. Therefore, sum = 495 + 491 + 40 = 1026.

提示:

  • 树中节点的数目在范围 [1, 1000]
  • 0 ≤ Node.val ≤ 9
  • 树的深度不超过10

思路

从根节点开始来一个左递归深度优先搜索,当遇到叶子节点后停止递归。

到了叶子节点后,使用秦九邵算法计算path的值。

代码

  1. /**
  2. * Definition for a binary tree node.
  3. * struct TreeNode {
  4. * int val;
  5. * TreeNode *left;
  6. * TreeNode *right;
  7. * TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8. * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9. * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10. * };
  11. */
  12. class Solution {
  13. public:
  14. int sumNumbers(TreeNode* root) {
  15. if( root == nullptr ) return 0;
  16. if( root->left == nullptr && root->right == nullptr ) return root->val;
  17. int sum = 0;
  18. vector<int> path;
  19. path.emplace_back( root->val );
  20. dfs(root, path, sum);
  21. return sum;
  22. }
  23. void dfs(TreeNode* node, vector<int>& path, int& sum) {
  24. // 1. Exit condition: leaf node
  25. if( node->left == nullptr && node->right == nullptr ) {
  26. sum += compute_sum(path);
  27. return;
  28. }
  29. // 2. Walk every node that not visited
  30. if( node->left != nullptr ) {
  31. path.emplace_back( node->left->val );
  32. dfs(node->left, path, sum);
  33. path.pop_back();
  34. }
  35. if( node->right != nullptr ) {
  36. path.emplace_back( node->right->val );
  37. dfs(node->right, path, sum);
  38. path.pop_back();
  39. }
  40. }
  41. int compute_sum(vector<int>& path) {
  42. int sum = 0;
  43. for(int i = 0; i < path.size(); i++) // QinJiuShao algorithm/Horner algorithm
  44. sum = sum * 10 + path[i];
  45. return sum;
  46. }
  47. };