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; }};新聞熱點
疑難解答
