leetcode: Path Sum II 迭代法

时间:2023-03-08 23:25:49
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.

通过一个p指针,遍历 二叉树,并将每次的值 保存在 sum2 中 。

遇到右节点,将右节点+depth 保存在 temp中,当再次使用 该节点时,根据depth 将sum2中的长度削减成 depth-1

/**
* Definition for a binary tree node.
* 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>> re;
if(root==NULL) return re;
TreeNode *p=root; int depth=;
vector<pair<TreeNode * ,int>> temp; // 保存右节点+depth
vector<int> sum2; // 保存一条路径的所有点值
pair<TreeNode *, int > t=make_pair(root,depth);
// temp.push_back(t);
while(!temp.empty()||p!=NULL){
sum2.push_back(p->val);
if(p->left!=NULL){
if(p->right!=NULL){
temp.push_back(make_pair(p->right,depth+));
}
p=p->left;
depth++;
}
else{
if(p->right==NULL){
int result=;
for(int i=;i<sum2.size();i++)
{
result=result+sum2[i];
}
if(result==sum)
re.push_back(sum2);
if(temp.empty()) break;
p=(*(temp.end()-)).first;
depth=(*(temp.end()-)).second;
temp.erase(temp.end()-);
sum2.erase(sum2.begin()+depth-,sum2.end());
}
else{
p=p->right;
depth++;
}
}
}
return re;
}
};