Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
For example:
Given the below binary tree and sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.
思路：树的题目，整体思路就是递归查找。三行解决。
bool hasPathSum(TreeNode *root, int sum) {
if(root == NULL) return false;
if(sum == root->val && (root->left == NULL) && (root->right == NULL)) return true; //和相等 且 是叶子结点
return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
}
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]
]
思路：找所有路径，也是用递归。发现满足的路径就压入。
vector<vector<int> > pathSum(TreeNode *root, int sum) {
vector<vector<int> > ans;
vector<int> tmpans;
findSum(root, sum, tmpans, ans);
return ans;
}
void findSum(TreeNode *root, int sum, vector<int> tmpans, vector<vector<int>> &ans)
{
if(root == NULL) return;
if(sum == root->val && (root->left == NULL) && (root->right == NULL)) //满足条件 压入答案
{
tmpans.push_back(root->val);
ans.push_back(tmpans);
}
else
{
tmpans.push_back(root->val);
}
findSum(root->left, sum - root->val, tmpans, ans);
findSum(root->right, sum - root->val, tmpans, ans);
}