当前位置: 首页 > 文档资料 > LeetCode 题解 >

Tree - Path Sum II

优质
小牛编辑
136浏览
2023-12-01

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.

For example:
Given the below binary tree and sum = 22.

  1. 5
  2. / \
  3. 4 8
  4. / / \
  5. 11 13 4
  6. / \ \
  7. 7 2 1

return

  1. [
  2. [5,4,11,2],
  3. [5,8,4,5]
  4. ]

题目翻译:
给定一个二叉树,并且给定一个值,找出所有从根节点到叶子节点和等于这个给定值的路径.上面的例子可以很好地让读者理解这个题目的目的.

解题思路:
这个题目和Path Sum的解法几乎是一模一样,都是用dfs来进行求解,不过就是在传参数的时候有些不同了,因为题目的要求也不同.

时间复杂度:
O(n)

代码如下:

  1. /**
  2. * Definition for binary tree
  3. * struct TreeNode {
  4. * int val;
  5. * TreeNode *left;
  6. * TreeNode *right;
  7. * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  8. * };
  9. */
  10. class Solution {
  11. public:
  12. vector<vector<int> > pathSum(TreeNode *root, int sum) {
  13. vector<vector<int>> ret;
  14. if(root == NULL)
  15. return ret;
  16. vector<int> curr;
  17. DFS(ret,curr,sum,0,root);
  18. return ret;
  19. }
  20. void DFS(vector<vector<int>>& ret, vector<int> curr, int sum, int tmpsum, TreeNode* root)
  21. {
  22. if(root == NULL)
  23. return;
  24. tmpsum+=root->val;
  25. curr.push_back(root->val);
  26. if(tmpsum == sum)
  27. {
  28. if(root->left == NULL&&root->right == NULL)
  29. {
  30. ret.push_back(curr);
  31. return;
  32. }
  33. }
  34. DFS(ret,curr,sum,tmpsum,root->left);
  35. DFS(ret,curr,sum,tmpsum,root->right);
  36. }
  37. };