LeetCode，[Leetcode] Path Sum II路徑和

2023-11-19 阅读 26 评论 0

摘要：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] ]題意：給定一數，

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();}
};