题目描述
二叉树中和为某一值的路径
样例
给出二叉树如下所示,并给出num=22。
5
/ \
4 6
/ / \
12 13 6
/ \ / \
9 1 5 1
输出:[[5,4,12,1],[5,6,6,5]]
算法1
(先序遍历)
在先序遍历的过程中,把遍历元素加入vector中,然后计算sum(这里直接减去sum即可省一个记录sum的变量)
当遇见叶子节点,并且sum值正好相等时,就把遍历的path压入结果,遍历完所有的路径,也就得到了最后的
答案。
具体详情看下述代码,和剑指offer书上一致
C++ 代码
class Solution {
public:
vector<vector<int>> ans;
vector<int> path;
void _findPath(TreeNode *root,int sum)
{
if(root == nullptr)
return;
if(root->left == root->right)
{
if(sum == root->val)
{
path.push_back(root->val);
ans.push_back(path);
path.pop_back();
}
return;
}
path.push_back(root->val);
_findPath(root->left,sum-root->val);
_findPath(root->right,sum-root->val);
path.pop_back();
}
vector<vector<int>> findPath(TreeNode* root, int sum) {
if(root == nullptr)
return {};
_findPath(root,sum);
return ans;
}
};