第一版代码,用了栈,然后把栈拷贝后逆序复制到数组中。其实可以不用栈的,省了栈和拷贝栈的空间。能直接把数组当栈使。
stack<TreeNode*> s;
void func(TreeNode* root, int sum, vector<vector<int> >& results) {
if (root == NULL)return;
s.push(root);
//如果遇到了符合条件的叶子节点。
if (root->val == sum && root->left == NULL && root->right == NULL) {
vector<int>result(s.size());
stack<TreeNode*> temp(s);
//将栈拷贝一份,然后逆序复制到数组中
for (int i = s.size() - 1; i >= 0; i--) {
result[i] = temp.top()->val;
temp.pop();
}
//将数组添加到总的结果中
results.push_back(result);
s.pop();
return;
}
func(root->left, sum - root->val, results);
func(root->right, sum - root->val, results);
s.pop();
return;
}
vector<vector<int> > FindPath(TreeNode* root, int expectNumber) {
vector<vector<int> > result;
if (root == NULL)
return result;
vector<vector<int> >results;
func(root, expectNumber, results);
return results;
}
第二版代码,参考了排行榜一的办法,将栈直接改成了用数组。内存使用一下低了很多。
//stack<TreeNode*> s;
vector<int>s;
void func(TreeNode* root, int sum, vector<vector<int> >& results) {
if (root == NULL)return;
s.push_back(root->val);
//如果遇到了符合条件的叶子节点。
if (root->val == sum && root->left == NULL && root->right == NULL) {
//stack<TreeNode*> temp(s);
//将栈拷贝一份,然后逆序复制到数组中
/* for (int i = s.size() - 1; i >= 0; i--) {
result[i] = temp.top()->val;
temp.pop();
}*/
//将数组添加到总的结果中
results.push_back(s);
s.pop_back();
return;
}
func(root->left, sum - root->val, results);
func(root->right, sum - root->val, results);
s.pop_back();
return;
}
vector<vector<int> > FindPath(TreeNode* root, int expectNumber) {
vector<vector<int> > result;
if (root == NULL)
return result;
vector<vector<int> >results;
func(root, expectNumber, results);
return results;
}

京公网安备 11010502036488号