给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。
例如，从根到叶子节点路径 1->2->3 代表数字 123。
计算从根到叶子节点生成的所有数字之和。
说明: 叶子节点是指没有子节点的节点。
示例 1:
输入: [1,2,3] 1 / \ 2 3 输出: 25 解释: 从根到叶子节点路径1->2代表数字12. 从根到叶子节点路径1->3代表数字13. 因此，数字总和 = 12 + 13 =25.
示例 2:
输入: [4,9,0,5,1] 4 / \ 9 0 / \ 5 1 输出: 1026 解释: 从根到叶子节点路径4->9->5代表数字 495. 从根到叶子节点路径4->9->1代表数字 491. 从根到叶子节点路径4->0代表数字 40. 因此，数字总和 = 495 + 491 + 40 = 1026.
思路：
这道题采用前序排序，然后用vector保存中间访问过的节点，如果当前访问的是叶节点，则直接计算vector中存储的对应的数字，不断累加到res中即可。所以需要三个函数：
int getVec(vector<int> vec) //得到vector中对应的数字 void sumNumbersCore(TreeNode* root, vector<int> vec, int &res) //前序遍历访问并保存节点，如果是叶节点调用getVec累加res int sumNumbers //主函数
代码如下：
int getVec(vector<int> vec) {
int result = 0;
for (int i = 0; i < vec.size(); i++) {
result = result * 10+vec[i];
}
return result;
}
void sumNumbersCore(TreeNode* root, vector<int> vec, int &res) {
if (!root) {
return;
}
vec.push_back(root->val);
if (!root->left && !root->right) {
res += getVec(vec);
return;
}
sumNumbersCore(root->left, vec, res);
sumNumbersCore(root->right, vec, res);
//vec.pop_back();
}
int sumNumbers(TreeNode* root) {
if (!root) {
return 0;
}
if (!root->left && !root->right) {
return root->val;
}
vector<int> vec;
int res = 0;
sumNumbersCore(root,vec, res);
return res;
}
注意vector声明的是值传递，在向上返回父节点时不会因为子函数修改了vector而发生改变，也就是说对于函数：
void sumNumbersCore(TreeNode* root, vector<int> vec, int &res) {
if (!root) {
return;
}
vec.push_back(root->val);
if (!root->left && !root->right) {
res += getVec(vec);
return;
}
sumNumbersCore(root->left, vec, res);
sumNumbersCore(root->right, vec, res);
//vec.pop_back();
}
无论子函数对vector做了增删改查或其他操作，最后执行完sumNumbersCore返回前，vector会恢复原样，所以我们无需对vector进行pop操作。如果对vector要进行引用传递，请用如下版本：
void sumNumbersCore(TreeNode* root, vector<int> &vec, int &res) {
if (!root) {
return;
}
vec.push_back(root->val);
if (!root->left && !root->right) {
res += getVec(vec);
return;
}
if (root->left) {
sumNumbersCore(root->left, vec, res);
vec.pop_back();
}
if (root->right) {
sumNumbersCore(root->right, vec, res);
vec.pop_back();
}
}
由于是引用传递，所以会保留子函数的修改记录，我们必须进行pop操作，恢复现场。
方法2：
由于我们需要一个vector保存遍历的节点，空间复杂度是O(n)，能不能把复杂度降为O(1)。答案是可以的。
采用递归的思想，每次先访问根节点，更新根节点为：
res = res * 10 + root->val;
然后对左右子树分别调用自身递归函数，分别相加左右子树的递归返回和。
代码如下：
int sumNumbersCore(TreeNode* root, int res) {
if (!root) {
return 0;
}
//vec.push_back(root->val);
res = res * 10 + root->val;
if (!root->left && !root->right) {
return res;
}
return sumNumbersCore(root->left, res) + sumNumbersCore(root->right, res);
}
int sumNumbers(TreeNode* root) {
if (!root) {
return 0;
}
if (!root->left && !root->right) {
return root->val;
}
int res = 0;
return sumNumbersCore(root, res);
}
这里要注意我们的返回值res必须声明成值传递，不能是引用传递，否则：
return sumNumbersCore(root->left, res) + sumNumbersCore(root->right, res);
在递归调用左子树时，res已经被左子树修改了，再把res传到右子树去计算时已经被修改了，不是根节点传入的res。
note：递归调用时我们经常会在函数参数中声明变量是引用或者值传递，声明引用类型是保证可以随递归调用不断修改自身的值。但是对于特殊情况一定要视情况而定（比如恢复现场，对于vector的pop操作，对于stack或者queue的pop操作等。。。）