题解 | #二叉树中和为某一值的路径(二)#
二叉树中和为某一值的路径(二)
https://www.nowcoder.com/practice/b736e784e3e34731af99065031301bca
第一版代码，用了栈，然后把栈拷贝后逆序复制到数组中。其实可以不用栈的，省了栈和拷贝栈的空间。能直接把数组当栈使。
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;
}
