Skip to content

Instantly share code, notes, and snippets.

@iwilbert
Created July 23, 2014 01:05
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save iwilbert/b42b689943beb2a1d3df to your computer and use it in GitHub Desktop.
Save iwilbert/b42b689943beb2a1d3df to your computer and use it in GitHub Desktop.
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