首页 > 代码库 > Leetcode Path Sum II
Leetcode 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]]
递归实现，注意递归实现时，放入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; }};
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。