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] ]
递归实现，注意递归实现时，放入vector中的数据，之后要pop_back出，此题中path参数没有使用引用，是按值传递的
class Solution { public: vector<vector<int> > res; void solvePathSum(TreeNode *root, int sum, vector<int> path){ if(root == NULL) return; if(root->left == NULL && root->right == NULL){ if(sum == root->val){ path.push_back(root->val); res.push_back(path); } return; } path.push_back(root->val); solvePathSum(root->left,sum-root->val,path); solvePathSum(root->right,sum-root->val,path); } vector<vector<int> > pathSum(TreeNode *root, int sum) { vector<int> path; solvePathSum(root,sum,path); return res; } };
非递归实现，在节点中添加了一个指向父节点的指针
class Solution { public: struct TreeNodeSum{ TreeNode *node; TreeNodeSum *parent; int sum; TreeNodeSum(TreeNode* node_, int sum_, TreeNodeSum* parent_ = NULL ):node(node_),sum(sum_),parent(parent_){} }; vector<vector<int> > pathSum(TreeNode *root, int sum) { vector<vector<int> >res; if(root == NULL) return res; queue<TreeNodeSum *> que; que.push(new TreeNodeSum(root,root->val)); while(!que.empty()){ TreeNodeSum *tmp = que.front();que.pop(); TreeNode *node = tmp->node; if(!node->left && !node->right && tmp->sum == sum){ vector<int> path; while(tmp){ path.push_back(tmp->node->val); tmp = tmp->parent; } reverse(path.begin(),path.end()); res.push_back(path); continue; } if(node->left){ TreeNodeSum *nodeSum = new TreeNodeSum(node->left,node->left->val+tmp->sum,tmp); que.push(nodeSum); } if(node->right ){ TreeNodeSum *nodeSum = new TreeNodeSum(node->right,node->right->val+tmp->sum,tmp); que.push(nodeSum); } } return res; } };
Leetcode Path Sum II,布布扣,bubuko.com
原文：http://www.cnblogs.com/xiongqiangcs/p/3818983.html
