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

递归+回溯

思路： 与（一）一样，也可以用递归加回溯。考虑深度优先递归前序遍历每一条路径，路径上的值依次累加并且依次保存到一个vector中，这样，当累加值等于目标值得时候（且当前节点是叶子节点时），就将此时的vector存下来；另外无论是否与目标值，在遍历完一条路径后都应该回溯（即将累加值减去当前节点值，并且从当前vector末尾删除当前值），将所有路径遍历完即获得结果。

class Solution {
public:
    void dfs(TreeNode* root,int& get,int expectNumber,vector<int>& tmp,vector<vector<int>>& ans){
        get+=root->val;//；累加当前值
        tmp.push_back(root->val);//将当前节点值保存在临时vector中
        if(root->left!=nullptr) dfs(root->left, get, expectNumber,tmp,ans); 
        if(root->right!=nullptr) dfs(root->right, get, expectNumber,tmp,ans);//深度优先遍历 
        if(root->left==nullptr && root->right==nullptr && get==expectNumber){
            ans.push_back(tmp);
        } //满足条件的路径则加入答案中
        get-=root->val;//无论是否满足条件均回溯
        tmp.pop_back();//从vector末尾删除当前节点值
    }
    
    vector<vector<int>> FindPath(TreeNode* root,int expectNumber) {
        vector<vector<int>> ans;
        if(root==nullptr) return ans;//根节点为空时，返回空
        int get=0;
        vector<int> tmp;
        dfs(root,get,expectNumber,tmp,ans);
        return ans;
    }
};
}

1. 时间复杂度： 由于需要遍历完所有节点，则时间复杂度为O(N)，其中N为节点数目
2. 空间复杂度： 用了一个临时的vector保存路径，空间大小等于树的高度H，递归深度也为树的高度，因此忽略返回结果的情况下，空间复杂度为O(H),若考虑空间复杂度，则最坏复杂度为O(N),即保存了所有节点，其中N为节点数目