Leetcode Path sum II
Path Sum II
Total Accepted: 6531
Total Submissions: 24225 My Submissions
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
return
再帰遡及法の応用である.2から3つ星の難易度.
次の手順に従います.
次のような書き方は、多くの再帰遡及プログラムの標準形式と言える.
Total Accepted: 6531
Total Submissions: 24225 My Submissions
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
, 5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
return
[
[5,4,11,2],
[5,8,4,5]
]
再帰遡及法の応用である.2から3つ星の難易度.
次の手順に従います.
vector<vector<int> > pathSum(TreeNode *root, int sum)
{
vector<vector<int> > rs;
vector<int> tmp;
storeSums(rs, tmp, root, sum);
return rs;
}
void storeSums(vector<vector<int> > &rs, vector<int> &tmp, TreeNode *r, int sum)
{
if (!r) return;
tmp.push_back(r->val);
storeSums(rs, tmp, r->left, sum - r->val);
storeSums(rs, tmp, r->right, sum - r->val);
if (!r->left && !r->right && r->val == sum) rs.push_back(tmp);
tmp.pop_back();
}
次のような書き方は、多くの再帰遡及プログラムの標準形式と言える.
//2014-2-17 update
vector<vector<int> > pathSum(TreeNode *root, int sum)
{
vector<vector<int> > rs;
vector<int> tmp;
path(rs, tmp, root, sum);
return rs;
}
void path(vector<vector<int> > &rs, vector<int> &tmp, TreeNode *r, int sum)
{
if (!r) return;
if (!r->left && !r->right)
{
if (r->val == sum)
{
rs.push_back(tmp);
rs.back().push_back(sum);
}
return;
}
tmp.push_back(r->val);
path(rs, tmp, r->left, sum - r->val);
path(rs, tmp, r->right, sum - r->val);
tmp.pop_back();
}