129. Sum Root to Leaf Numbers
1.問題
給予一個binary tree, 計算所有路徑的總和

2.想法
提問
function header, parameter
test input
觀察
DFS, 當到達盡頭時計算總和
總和要用long
說明想法
測試計算複雜度
3.程式碼
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int sumNumbers(TreeNode* root) {
if (!root) {
return 0;
}
vector<vector<int>> res;
vector<int> record;
long minVal = 0;
getPaths(root, record, minVal);
return minVal;
}
private:
void getPaths(TreeNode* root, vector<int> record, long& sum) {
if (!root) {
return;
}
if (!root->left && !root->right) {
record.push_back(root->val);
long tmpSum = 0;
for (int i = 0; i < record.size(); i++) {
tmpSum += (record[i] * pow (10, record.size() - 1 - i));
}
sum += tmpSum;
return;
}
if (root->left) {
record.push_back(root->val);
getPaths(root->left, record, sum);
record.pop_back();
}
if (root->right) {
record.push_back(root->val);
getPaths(root->right, record, sum);
record.pop_back();
}
}
};
Last updated