Created
July 23, 2014 01:05
-
-
Save iwilbert/b42b689943beb2a1d3df to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public void allPaths(TreeNode root, int target) { | |
if (root == null) | |
return; | |
int dep = depth(root); | |
int[] path = new int[dep]; | |
findPaths(root, target, 0, path); | |
} | |
private void findPaths(TreeNode root, int target, int level, int[] path) { | |
if (root == null) | |
return; | |
path[level] = root.val; | |
int sum = 0; | |
for (int i = level; i >= 0; i--) { | |
sum += path[i]; | |
if (sum == target) | |
printPath(path, i, level); | |
} | |
findPaths(root.left, target, level+1, path); | |
findPaths(root.right, target, level+1, path); | |
} | |
private void printPath(int[] path, int i, int j) { | |
System.out.print(path[i]); | |
for (int k = i+1; k <= j; k++) | |
System.out.print(" -> " + path[k]); | |
System.out.println(); | |
} | |
private int depth(TreeNode root) { | |
if (root == null) | |
return 0; | |
return Math.max(depth(root.left), depth(root.right)) + 1; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment