本题和113.路径总和II是类似的思路，做完这道题，可以顺便把113.路径总和II 和 112.路径总和 做了。
结合112.路径总和 和 113.路径总和II，我在讲了二叉树：递归函数究竟什么时候需要返回值，什么时候不要返回值？，如果大家对二叉树递归函数什么时候需要返回值很迷茫，可以看一下。
接下来在看本题，就简单多了，本题其实需要使用回溯，但一些同学可能都不知道自己用了回溯，在二叉树：以为使用了递归，其实还隐藏着回溯中，我详细讲解了二叉树的递归中，如何使用了回溯。
接下来我们来看题：
首先思路很明确，就是要遍历整个树把更节点到叶子节点组成的数字相加。
那么先按递归三部曲来分析：
如果对递归三部曲不了解的话，可以看这里：二叉树：前中后递归详解
- 确定递归函数返回值及其参数
这里我们要遍历整个二叉树，且需要要返回值做逻辑处理，所有返回值为void，在二叉树：递归函数究竟什么时候需要返回值，什么时候不要返回值？中，详细讲解了返回值问题。
参数只需要把根节点传入，此时还需要定义两个全局遍历，一个是result，记录最终结果，一个是vector path。
为什么用vector类型（就是数组）呢？ 因为用vector方便我们做回溯！
所以代码如下：
int result;
vector<int> path;
void traversal(TreeNode* cur)
- 确定终止条件
递归什么时候终止呢？
当然是遇到叶子节点，此时要收集结果了，通知返回本层递归，因为单条路径的结果使用vector，我们需要一个函数vectorToInt把vector转成int。
终止条件代码如下：
if (!cur->left && !cur->right) { // 遇到了叶子节点
result += vectorToInt(path);
return;
}
这里vectorToInt函数就是把数组转成int，代码如下：
int vectorToInt(const vector<int>& vec) {
int sum = 0;
for (int i = 0; i < vec.size(); i++) {
sum = sum * 10 + vec[i];
}
return sum;
}- 确定递归单层逻辑
本题其实采用前中后序都不无所谓， 因为也没有中间几点的处理逻辑。
这里主要是当左节点不为空，path收集路径，并递归左孩子，右节点同理。
但别忘了回溯。
如图：
代码如下：
// 中
if (cur->left) { // 左 （空节点不遍历）
path.push_back(cur->left->val);
traversal(cur->left); // 递归
path.pop_back(); // 回溯
}
if (cur->right) { // 右 （空节点不遍历）
path.push_back(cur->right->val);
traversal(cur->right); // 递归
path.pop_back(); // 回溯
}这里要注意回溯和递归要永远在一起，一个递归，对应一个回溯，是一对一的关系，有的同学写成如下代码：
if (cur->left) { // 左 （空节点不遍历）
path.push_back(cur->left->val);
traversal(cur->left); // 递归
}
if (cur->right) { // 右 （空节点不遍历）
path.push_back(cur->right->val);
traversal(cur->right); // 递归
}
path.pop_back(); // 回溯把回溯放在花括号外面了，世界上最遥远的距离，是你在花括号里，而我在花括号外！ 这就不对了。
关键逻辑分析完了，整体C++代码如下：
class Solution {
private:
int result;
vector<int> path;
// 把vector转化为int
int vectorToInt(const vector<int>& vec) {
int sum = 0;
for (int i = 0; i < vec.size(); i++) {
sum = sum * 10 + vec[i];
}
return sum;
}
void traversal(TreeNode* cur) {
if (!cur->left && !cur->right) { // 遇到了叶子节点
result += vectorToInt(path);
return;
}
if (cur->left) { // 左 （空节点不遍历）
path.push_back(cur->left->val); // 处理节点
traversal(cur->left); // 递归
path.pop_back(); // 回溯，撤销
}
if (cur->right) { // 右 （空节点不遍历）
path.push_back(cur->right->val); // 处理节点
traversal(cur->right); // 递归
path.pop_back(); // 回溯，撤销
}
return ;
}
public:
int sumNumbers(TreeNode* root) {
path.clear();
if (root == nullptr) return 0;
path.push_back(root->val);
traversal(root);
return result;
}
};过于简洁的代码，很容易让初学者忽视了本题中回溯的精髓，甚至作者本身都没有想清楚自己用了回溯。
我这里提供的代码把整个回溯过程充分体现出来，希望可以帮助大家看的明明白白！
Java：
Python：
class Solution:
def sumNumbers(self, root: TreeNode) -> int:
res = 0
path = []
def backtrace(root):
nonlocal res
if not root: return # 节点空则返回
path.append(root.val)
if not root.left and not root.right: # 遇到了叶子节点
res += get_sum(path)
if root.left: # 左子树不空
backtrace(root.left)
if root.right: # 右子树不空
backtrace(root.right)
path.pop()
def get_sum(arr):
s = 0
for i in range(len(arr)):
s = s * 10 + arr[i]
return s
backtrace(root)
return resGo：
JavaScript：
