给你一个二叉树的根节点 root ,树中每个节点都存放有一个 0 到 9 之间的数字。
每条从根节点到叶节点的路径都代表一个数字:
例如,从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。
计算从根节点到叶节点生成的 所有数字之和 。
叶节点 是指没有子节点的节点。
输入:root = [1,2,3]
输出:25
解释:
从根到叶子节点路径 1->2 代表数字 12
从根到叶子节点路径 1->3 代表数字 13
因此,数字总和 = 12 + 13 = 25
> 代码
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;
}
};
标签:cur,int,back,求根,path,129,root,节点
From: https://www.cnblogs.com/lihaoxiang/p/17536070.html