113. Path Sum II
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]
]思路：
先序遍历，获取目标序列存到结果序列中。
代码如下：
/**
* Definition for a binary tree node.
* 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) {
vector<vector<int>> result;
vector<TreeNode *> temp;
DFS(root,result,temp,0,sum);
return result;
}
void DFS(TreeNode* root,vector<vector<int>> &result,vector<TreeNode *> &tempNodePtr ,int curTotal , int sum)
{
if(!root)
return;
curTotal += root->val;
tempNodePtr.push_back(root);
vector<int> tempInt;
if( !root->left && !root->right && curTotal == sum)
{
for(int i = 0 ; i < tempNodePtr.size(); i++)
{
tempInt.push_back(tempNodePtr[i]->val);
}
result.push_back(tempInt);
tempInt.clear();
}
vector<TreeNode *> tempNodePtrLeft(tempNodePtr);
vector<TreeNode *> tempNodePtrRight(tempNodePtr);
DFS(root->left,result,tempNodePtrLeft,curTotal,sum);
DFS(root->right,result,tempNodePtrRight,curTotal,sum);
}
};2016-08-07 13:52:07
亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
