题目链接

题目描述：

给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。

例如，从根到叶子节点路径 1->2->3 代表数字 123。

计算从根到叶子节点生成的所有数字之和。

说明: 叶子节点是指没有子节点的节点。

实例：
129求根到叶子节点数字之和 - 图1

解题思路

  与#257思路类似，套用先序遍历框架，将焦点移到对当前结点的操作和对传入参数对设置，剩下的交给递归。

  1. 判断当前结点是否为叶子结点。如果是，显然意味着一趟路径已然完成，将这一趟的路径和传给总数和sum。之后return回上一层(叶子结点的父结点)，换路继续递归找出其与路径和(有回溯的思想在其中)。
  2. 既然有回溯的思想，那显然会出现状态重置的部分。而且根据本题题意，需要设置暂时存储的变量用于存储每一条路径和。对于该问题，可以通过添加辅助函数，扩展一个参数cur，用于暂时存储每一条路径和，然后在其传入参数的赋值部分，由于一开始就赋上当前结点的值，因此后面递归的赋值也要赋上左右子节点的值。注意：递归蕴含着栈的思想，每个结点，只有当与它相关的左右子树全部遍历完成才会返回它的父结点，也就是说返回之前它自己的cur是一直存在的。

乘10自增，执行用时：4ms

  1. class Solution {
  2. public:
  3.     int sumNumbers(TreeNode* root) {
  4.         if(!root)
  5.             return sum;
  7.         helper(root, root->val);   //提前赋值，后面递归的赋值也要相应改变
  8.         return sum;
  9.     }
  11.     void helper(TreeNode* root, int cur){      //cur表示每一条路径和
  12.         if(!root)
  13.             return;
  15.         if(!root->left && !root->right){
  16.             sum += cur;
  17.             return;
  18.         }
  20.         if(root->left)
  21.             helper(root->left, cur * 10 + root->left->val);
  22.         if(root->right)
  23.             helper(root->right, cur * 10 + root->right->val);
  25.         return;
  26.     }
  28. private:
  29.     int sum = 0;    //记录所有和
  30. };
  1. class Solution {
  2. public:
  3.     int sumNumbers(TreeNode* root) {
  4.         if(!root)
  5.             return sum;
  7.         helper(root, to_string(root->val));
  8.         return sum;
  9.     }
  11.     void helper(TreeNode* root, string cur){
  12.         if(!root)
  13.             return;
  15.         if(!root->left && !root->right){
  16.             //字符串转int
  17.             stringstream ss;
  18.             int curNum;
  19.             ss << cur;
  20.             ss >> curNum;
  22.             sum += curNum;
  23.             return;
  24.         }
  26.         if(root->left)
  27.             helper(root->left, cur + to_string(root->left->val));
  28.         if(root->right)
  29.             helper(root->right, cur + to_string(root->right->val));
  31.         return;
  32.     }
  34. private:
  35.     int sum = 0;
  36. };

如果有错误或者不严谨的地方，请务必给予指正，十分感谢。