来源:力扣(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))。
评论