Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.
For example:
Given the below binary tree and sum = 22,
return
這個題目適合用遞歸來解，我的C++代碼實現如下：
class Solution {
public:
vector > pathSum(TreeNode *root, int sum) {
vector > paths;
vector curr_path;
if (!root) return paths;
find(root, sum, paths, curr_path);
return paths;
}
private:
void find(TreeNode *root, int sum, vector > &paths, vector &curr_path) {
curr_path.push_back(root->val);
if (root->left == nullptr && root->right == nullptr)
if (root->val == sum) paths.push_back(curr_path);
if (root->left) {
find(root->left, sum - root->val, paths, curr_path);
curr_path.pop_back();
}
if (root->right) {
find(root->right, sum - root->val, paths, curr_path);
curr_path.pop_back();
}
}
}; 時間性能如下圖所示：
