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>> res; if (!root) return res; vector<int> out; helper(res, out, sum, root); return res; } void helper(vector<vector<int>>& res, vector<int>& out, int sum, TreeNode *node) { if (!node) return; out.push_back(node->val); if (sum == node->val && !node->left && !node->right) res.push_back(out); sum = sum - node->val; if (node->left) helper(res, out, sum, node->left); if (node->right) helper(res, out, sum, node->right); out.pop_back(); } };
原文：http://www.cnblogs.com/yuanluo/p/7639076.html