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 andsum = 22,
5/ \4 8/ / \11 13 4/ \ / \7 2 5 1
return
[[5,4,11,2],[5,8,4,5] ]
題意:給定一數,在樹中找出所有路徑和等于該數的情況。
方法一:
使用vector向量實現stack的功能,以方便輸出指定路徑。思想和代碼和Path sum大致相同。
/*** 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>> res;vector<TreeNode *> vec;TreeNode *pre=NULL;TreeNode *cur=root;int temVal=0;while(cur|| !vec.empty()){while(cur){vec.push_back(cur);temVal+=cur->val;cur=cur->left;}cur=vec.back();if(cur->left==NULL&&cur->right==NULL&&temVal==sum){ //和Path sum最大的區別vector<int> temp;for(int i=0;i<vec.size();++i)temp.push_back(vec[i]->val);res.push_back(temp);}if(cur->right&&cur->right !=pre)cur=cur->right;else{vec.pop_back();temVal-=cur->val;pre=cur;cur=NULL;}} return res; } };
方法二:遞歸法
?
/*** 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>> res;vector<int> path;findPaths(root,sum,res,path);return res;}void findPaths(TreeNode *root,int sum,vector<vector<int>> &res,vector<int> &path){if(root==NULL) return;path.push_back(root->val);if(root->left==NULL&&root->right==NULL&&sum==root->val)res.push_back(path);findPaths(root->left,sum-root->val,res,path);findPaths(root->right,sum-root->val,res,path);path.pop_back();} };
LeetCode。?