leetcode

0 // Brute force

1 class Solution {

2 public:

3 int pathSum(TreeNode *root, int targetSum) {

4 if (!root) return 0;

5

6 stack<TreeNode *> st;

7 queue<TreeNode *> q;

8

9 st.push(root);

10 while (!st.empty()) {

11 TreeNode *root = st.top();

12 st.pop();

13 q.push(root);

14 if (root->left) st.push(root->left);

15 if (root->right) st.push(root->right);

16 }

17

18 int res = 0;

19 while (!q.empty()) {

20 stack<pair<TreeNode *, long long>> st;

21 st.push({q.front(), 0});

22 q.pop();

23 while (!st.empty()) {

24 auto [root, sum] = st.top();

25 st.pop();

26 sum += root->val;

27 if (sum == targetSum) res++;

28 if (root->left) st.push({root->left, sum});

29 if (root->right) st.push({root->right, sum});

30 }

31 }

32

33 return res;

34 }

35 };

36

37 // Optimized

38 class Solution {

39 public:

40 int pathSum(TreeNode *root, int targetSum) {

41 if (!root) return 0;

42 queue<pair<TreeNode *, vector<long long>>> q;

43 int res = 0;

44

45 q.push({root, {}});

46 while (!q.empty()) {

47 auto &[root, vec] = q.front();

48 long long sum = root->val + (vec.size() ? vec.back() : 0);

49

50 for (int num : vec)

51 if (sum - num == targetSum) res++;

52 if (sum == targetSum) res++;

53

54 if (root->left) {

55 q.push({root->left, vec});

56 q.back().second.push_back(sum);

57 }

58

59 if (root->right) {

60 q.push({root->right, vec});

61 q.back().second.push_back(sum);

62 }

63

64 q.pop();

65 }

66

67 return res;

68 }

69 };