LeetCode | Path Sum II
2176 ワード
タイトル:
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]
]
考え方:
再帰的手法により,左右のサブノードがNULLである場合,現在のノードがリーフノードであると判断できる.に似ているhttp://blog.csdn.net/lanxu_yy/article/details/11787805
コード: /**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> pathSum(TreeNode *root, int sum) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector<vector<int>>* v = new vector<vector<int>>();
if(root == NULL)
{
return *v;
}
vector<int> tmp;
pathSum(root, 0, sum, tmp, v);
return *v;
}
void pathSum(TreeNode * p, int total, int sum, vector<int> tmp, vector<vector<int>> * v)
{
if((p->left == NULL) && (p->right == NULL))
{
if(total + p->val == sum)
{
tmp.push_back(p->val);
v->push_back(tmp);
}
}
else if(p->left == NULL)
{
tmp.push_back(p->val);
pathSum(p->right, p->val + total, sum, tmp, v);
}
else if(p->right == NULL)
{
tmp.push_back(p->val);
pathSum(p->left, p->val + total, sum, tmp, v);
}
else
{
tmp.push_back(p->val);
pathSum(p->left, p->val + total, sum, tmp, v);
pathSum(p->right, p->val + total, sum, tmp, v);
}
}
};
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
[
[5,4,11,2],
[5,8,4,5]
]
再帰的手法により,左右のサブノードがNULLである場合,現在のノードがリーフノードであると判断できる.に似ているhttp://blog.csdn.net/lanxu_yy/article/details/11787805
コード: /**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> pathSum(TreeNode *root, int sum) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector<vector<int>>* v = new vector<vector<int>>();
if(root == NULL)
{
return *v;
}
vector<int> tmp;
pathSum(root, 0, sum, tmp, v);
return *v;
}
void pathSum(TreeNode * p, int total, int sum, vector<int> tmp, vector<vector<int>> * v)
{
if((p->left == NULL) && (p->right == NULL))
{
if(total + p->val == sum)
{
tmp.push_back(p->val);
v->push_back(tmp);
}
}
else if(p->left == NULL)
{
tmp.push_back(p->val);
pathSum(p->right, p->val + total, sum, tmp, v);
}
else if(p->right == NULL)
{
tmp.push_back(p->val);
pathSum(p->left, p->val + total, sum, tmp, v);
}
else
{
tmp.push_back(p->val);
pathSum(p->left, p->val + total, sum, tmp, v);
pathSum(p->right, p->val + total, sum, tmp, v);
}
}
};
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> pathSum(TreeNode *root, int sum) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector<vector<int>>* v = new vector<vector<int>>();
if(root == NULL)
{
return *v;
}
vector<int> tmp;
pathSum(root, 0, sum, tmp, v);
return *v;
}
void pathSum(TreeNode * p, int total, int sum, vector<int> tmp, vector<vector<int>> * v)
{
if((p->left == NULL) && (p->right == NULL))
{
if(total + p->val == sum)
{
tmp.push_back(p->val);
v->push_back(tmp);
}
}
else if(p->left == NULL)
{
tmp.push_back(p->val);
pathSum(p->right, p->val + total, sum, tmp, v);
}
else if(p->right == NULL)
{
tmp.push_back(p->val);
pathSum(p->left, p->val + total, sum, tmp, v);
}
else
{
tmp.push_back(p->val);
pathSum(p->left, p->val + total, sum, tmp, v);
pathSum(p->right, p->val + total, sum, tmp, v);
}
}
};