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 1return
[ [5,4,11,2], [5,8,4,5]]s思路： 1. 和Leetcode 112. Path Sum相似。区别是要列举所有的路径！基本思路还是PReorder，但是需要一个vector< int>把每次遍历的数放入或者弹出，当判断path sum为所求，则把这个vector保存起来。
//方法１：recursive：class Solution {public: void helper(vector<vector<int>>&res,TreeNode* root,vector<int> cur,int sum) { // if(!root) return; cur.push_back(root->val);//中 if(!root->left&&!root->right){ if(root->val==sum)res.push_back(cur); return; } helper(res,root->left,cur,sum-root->val);//左 helper(res,root->right,cur,sum-root->val);//右 //cur.pop_back(); } vector<vector<int>> pathSum(TreeNode* root, int sum) { vector<vector<int>> res; //vector<int> cur; helper(res,root,{},sum); return res; }};//方法１：变形的做法.上面方法用vector<int> cur，这个方法用vector<int>&curclass Solution {public: void helper(vector<vector<int>>&res,TreeNode* root,vector<int>&cur,int sum) { // if(!root) return; cur.push_back(root->val);//中 if(!root->left&&!root->right){ if(root->val==sum)res.push_back(cur); //return; } helper(res,root->left,cur,sum-root->val);//左 helper(res,root->right,cur,sum-root->val);//右 cur.pop_back(); } vector<vector<int>> pathSum(TreeNode* root, int sum) { vector<vector<int>> res; vector<int> cur; helper(res,root,cur,sum); return res; }};//方法2：iterative.用stack,preorder,用cur和pre两个指针。其实都是套路。class Solution {public: vector<vector<int>> pathSum(TreeNode* root, int sum) { stack<TreeNode*> ss; TreeNode* pnow=root,*pre=NULL; vector<vector<int>> res; vector<int> cur; int path=0; while(pnow||!ss.empty()){ while(pnow){ path+=pnow->val; cur.push_back(pnow->val); ss.push(pnow); pnow=pnow->left; } pnow=ss.top(); if(!pnow->left&&!pnow->right&&path==sum){ res.push_back(cur); } if(pnow->right&&pnow->right!=pre){ pnow=pnow->right; }else{ pre=pnow; path-=pnow->val; ss.pop(); cur.pop_back(); pnow=NULL; } } return res; }};新闻热点
疑难解答
