题解 | #二叉树根节点到叶子节点和为指定值的路径#
二叉树根节点到叶子节点和为指定值的路径
http://www.nowcoder.com/practice/840dd2dc4fbd4b2199cd48f2dadf930a
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
class Solution {
public:
/**
*
* @param root TreeNode类
* @param sum int整型
* @return int整型vector<vector<>>
*/
vector<vector<int> > pathSum(TreeNode* root, int sum) {
// write code here
if (!root)
return {};
target = sum;
vector<int> r;
r.push_back(root->val);
digui(root, r);
return re;
}
void digui(TreeNode* x, vector<int> r)
{
if (x->left != NULL)
{
vector<int> r1 = r;
r1.push_back(x->left->val);
x->left->val = x->val + x->left->val;
digui(x->left, r1);
}
if (x->right != NULL)
{
vector<int> r2 = r;
r2.push_back(x->right->val);
x->right->val = x->val + x->right->val;
digui(x->right, r2);
}
if (x->left == NULL && x->right == NULL)
{
if (x->val == target)
re.push_back(r);
}
}
private:
int target;
vector<vector<int> > re;//各组从根到叶的记录
}; 