来源：力扣 （LeetCode）
链接：113. 路径总和 II
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
一、题目描述
给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
说明：叶子节点是指没有子节点的节点。
示例:
给定如下二叉树，以及目标和 sum = 22：
|
1 2 3 4 5 6 7 |
5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1 |
返回:
|
1 2 3 4 |
[ [5,4,11,2], [5,8,4,5] ] |
二、题解
说明：
此题是112. 路径总和Ⅰ的升级版 （题解参考：113-路径总和Ⅰ），相对于第一题来说，有以下两点不通：
- 题Ⅰ只需要判断存在即可，该题需要找到所有可能的结果。
- 找到所有结果的同时，该题还需要保存所有的路径。
算法：
递归+深搜遍历所有的树节点，每遍历一个节点除了计算 sum 是否满足条件以外，还要记录下该节点。当遇到满足条件的叶节点，把当前路径加到结果中去。需要利用到两个辅助的数组。
代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
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)) 。