FilesExpand file tree

 master

/

PathSumIII.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

64 lines (57 loc) · 1.65 KB

 master

/

PathSumIII.java

Copy path

Top

File metadata and controls

• Code
• Blame

64 lines (57 loc) · 1.65 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

package tree;

import java.util.HashMap;

import java.util.Map;

/**

* Created by gouthamvidyapradhan on 08/04/2017. You are given a binary tree in which each node

* contains an integer value.

*

* <p>Find the number of paths that sum to a given value.

*

* <p>The path does not need to start or end at the root or a leaf, but it must go downwards

* (traveling only from parent nodes to child nodes).

*

* <p>The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

*

* <p>Example:

*

* <p>root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

*

* <p>10 / \ 5 -3 / \ \ 3 2 11 / \ \ 3 -2 1

*

* <p>Return 3. The paths that sum to 8 are:

*

* <p>1. 5 -> 3 2. 5 -> 2 -> 1 3. -3 -> 11

*/

public class PathSumIII {

/** */

public static class TreeNode {

int val;

TreeNode left;

TreeNode right;

TreeNode(int x) {

val = x;

}

}

private Map<Integer, Integer> pathCount = new HashMap<>();

private int totalCount;

public static void main(String[] args) throws Exception {

TreeNode node = new TreeNode(1);

System.out.println(new PathSumIII().pathSum(node, 0));

}

public int pathSum(TreeNode root, int sum) {

if (root == null) return 0;

dfs(root, sum, 0);

return totalCount;

}

private void dfs(TreeNode root, int target, int pSum) {

if (root != null) {

pSum += root.val;

if (pSum == target) totalCount++;

totalCount += pathCount.getOrDefault(pSum - target, 0);

pathCount.put(pSum, pathCount.getOrDefault(pSum, 0) + 1);

dfs(root.left, target, pSum);

dfs(root.right, target, pSum);

pathCount.put(pSum, pathCount.get(pSum) - 1);

}

}

}