非递归方法:
class Solution {
public:
vector<vector<int>> FindPath(TreeNode* root,int expectNumber) {
vector<vector<int>> result;
if(!root)
return result;
stack<TreeNode *> s;
s.push(root);
TreeNode *cur=root;
TreeNode *last=NULL;
vector<int> curpath;
int sum=;
while(!s.empty())
{
if(cur==NULL)
{
if((s.top())->right&&(s.top())->right!=last)
{
cur=(s.top())->right;
}
else
{
last=s.top();
s.pop();
sum-=last->val;
curpath.pop_back();
}
}
else
{
s.push(cur);
curpath.push_back(cur->val);
sum+=cur->val;
if(!cur->left&&!cur->right&&sum==expectNumber)
{
result.push_back(curpath);
}
cur=cur->left;
}
}
return result;
}
};
要注意转向右子树时的情况！！
对容器vector，push_back()是从容器末尾插入元素，pop_back()是从容器末尾删除元素。stack没有迭代器，只能插入和得到栈顶元素。
递归方法如下：
class Solution {
public:
vector<vector<int>> FindPath(TreeNode* root,int expectNumber) {
vector<vector<int>> result;
if(!root)
return result;
int cursum=;
vector<int> path;
FindPath(root,expectNumber, result, path, cursum);
return result;
}
void FindPath(TreeNode* root, int expectNumber, vector<vector<int>> &result, vector<int> &path, int cursum)
{
cursum+=root->val;
path.push_back(root->val);
if(!root->left&&!root->right&&cursum==expectNumber)
{
result.push_back(path);
}
if(root->left!=NULL)
FindPath(root->left,expectNumber, result, path, cursum);
if(root->right!=NULL)
FindPath(root->right,expectNumber, result, path, cursum);
path.pop_back();
}
};