来源：力扣（LeetCode）

链接：113. 路径总和 II

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、题目描述

给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

说明：叶子节点是指没有子节点的节点。

示例:

给定如下二叉树，以及目标和 sum = 22：

          5
         / \
        4   8
       /   / \
      11  13  4
     /  \    / \
    7    2  5   1

返回:

[
   [5,4,11,2],
   [5,8,4,5]
]

二、题解

说明：

此题是112. 路径总和Ⅰ的升级版（题解参考：），相对于第一题来说，有以下两点不通：

1. 题Ⅰ只需要判断存在即可，该题需要找到所有可能的结果。
2. 找到所有结果的同时，该题还需要保存所有的路径。

算法：

递归+深搜遍历所有的树节点，每遍历一个节点除了计算sum是否满足条件以外，还要记录下该节点。当遇到满足条件的叶节点，把当前路径加到结果中去。需要利用到两个辅助的数组。

代码：

class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        dfs(root, sum);
        return m_ans;
    }
private:
    void dfs(TreeNode *root, int sum) {
        if(root == NULL) {
            return;
        }

        // 节点添加到临时的数组里面去
        m_vec.push_back(root->val);
        sum -= root->val;

        if (root->left == NULL && root->right == NULL && sum == 0) {
            // 当前临时数组加入到结果数组中
            m_ans.push_back(m_vec);
        }

        // 遍历左节点
        if (root->left) {
            dfs(root->left, sum);
        }
        
        // 遍历右节点
        if (root->right) {
            dfs(root->right, sum);
        }
        
        // 最关键的一步：回溯状态
        // 函数入口处把当前节点添加到临时数组里面去了，这里退出的时候要删掉这一个节点
        // 避免当前节点还存在于临时数组中，影响后续的遍历结果
        m_vec.pop_back();
    }

    vector<vector<int>> m_ans; // 保存所有的结果
    vector<int> m_vec; // 临时保存路径的数组
};

复杂度分析：

• 时间复杂度：访问每个节点一次，时间复杂度为O(N) ，其中N是节点个数。
• 空间复杂度：需要用到两个数组，其中一个是保存结果的数组可不算入空间占用，另外一个保存路径的临时数组最坏情况下（树是一条线，即类似链表的时候）占用O(N) ，平均和最优情况下（树是平衡树）占用O(log(N))。