题解 | #二叉树中和为某一值的路径(二)#

1. 递归做法：
   1. 如果当前节点和等于期望值且为叶子节点，则返回；
   2. 否则递归到下一层寻找

注意递归函数结尾需要将当前节点出栈（非尾递归，则函数尾部需要考虑完整操作）

class Solution {
public:
    vector<vector<int>> vv;
    vector<int> v;
    vector<vector<int>> FindPath(TreeNode* root,int expectNumber) {
        dfs(root, expectNumber);
        return vv;
    }
    
    void dfs(TreeNode* root, int sum){
        if(!root)
            return;
        v.push_back(root->val);
        if(root->val == sum && !root->left && !root->right)
            vv.push_back(v);
        else{
            dfs(root->left, sum - root->val);
            dfs(root->right, sum - root->val);
        }
        v.pop_back();
    }
};

2. 非递归做法：

后序遍历的非递归做法有个特性：当遍历到某个节点时，栈中保存的是根节点到该节点的路径。

基于此，可以在后序遍历的非递归方法中插入当前路径和与期望值的比较。

class Solution {
public:
    vector<vector<int>> FindPath(TreeNode* root,int expectNumber) {
        // write code here
        vector<vector<int>> res;
        vector<TreeNode*> s;
        TreeNode* temp = root, * pre = NULL;
        int count = 0;
        while(!s.empty() || temp){
            while(temp){
                count += temp->val;
                s.push_back(temp);
                temp = temp->left;
            }
            temp = s.back();
            if(temp->right && temp->right != pre){
                temp = temp->right;
            }
            else{
                if(count == expectNumber && !temp->left && !temp->right)
                    res.push_back(trans(s));
                count -= temp->val;
                s.pop_back();
                pre = temp;
                temp = NULL;
            }
        }
        return res;
    }
     
    vector<int> trans(vector<TreeNode*> root){
        vector<int> res;
        for(int i = 0;i < root.size(); i ++)
            res.push_back(root[i]->val);
        return res;
    }
};