Given a binary tree and a sum, find all root-to-leaf paths where each path‘s sum equals the given sum.
For example:sum = 22,
5
/ 4 8
/ / 11 13 4
/ \ / 7 2 5 1
return
[ [5,4,11,2], [5,8,4,5] ]
解体思路：利用递归深度优先遍历，保存中间结果。
/** * Definition for binary tree * 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<int> intermediate; dfs(root, sum, intermediate, result); return result; } void dfs(TreeNode *root, int gap, vector<int> &intermediate, vector<vector<int> > &result){ if(root == nullptr) return; intermediate.push_back(root->val); if(root->left == nullptr && root->right == nullptr){ if(gap == root->val) result.push_back(intermediate); } dfs(root->left, gap - root->val, intermediate, result); dfs(root->right, gap - root->val, intermediate, result); intermediate.pop_back();//弹出回退 } };
原文：http://www.cnblogs.com/zxy1992/p/4386852.html