Question (in Chinese): http://ac.jobdu.com/problem.php?pid=1368
Question Name: Path In Tree
Question Description: Given a binary tree and a value, show all the paths, whose sum is equal to the given value. A path is defined as the route from root to one leaf.
Input: the input might contain multiple test cases. Each test case includes N+1 lines. Inside each test case, the first line includes two intergers N and K (0 <= N <= 10000). N is the number of nodes in that tree. And K is the wanted sum. The following N lines contain three integers in each line as vi, leftnode, and rightnode. vi is the value of the i(th) node. leftnode and rightnode are the indexes of i(th) node’s left son and right son respectively. -1 means no such son.
Output: firstly print out a line “result:”, then print out all the qualified paths lexicographically.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | Input: 5 22 10 2 3 5 4 5 12 -1 -1 4 -1 -1 7 -1 -1 1 5 1 -1 -1 Output: result: A path is found: 1 2 5 A path is found: 1 3 result: |
The solution is:
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 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 | /*---------------------------------------------------------------- * Author: Sheng Yu codesays.com * Written: 08/16/2014 * Last updated: 08/16/2014 * * Filename: PathInTree.java * Compilation: javac PathInTree.java * Execution: java PathInTree * JDK Used: 1.7 *----------------------------------------------------------------*/ import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.StreamTokenizer; import java.util.Stack; /** * The utility to find all paths in a tree, whose sum is a given value. * @author Sheng Yu codesays.com * */ public class PathInTree { /** * The definition of binary tree. * @author Sheng Yu codesays.com * @param <T> the type of the value in the node. */ private static class BinaryTreeNode<T> { /** The value of current node. */ private T value = null; /** The left of current node. */ private BinaryTreeNode<T> left = null; /** The position of the node in the array */ private int position = 0; /** The right son of current node. */ private BinaryTreeNode<T> right = null; /** @return the value of this node. */ public T getValue() { return value; } /** @param newValue the new value of this node. */ public void setValue(final T newValue) { value = newValue; } /** @return the position of this node. */ public int getPos() { return position; } /** @param newPos the new value of this node. */ public void setPos(final int newPos) { position = newPos; } /** @return the left son of this node. */ public BinaryTreeNode<T> getLeft() { return left; } /** @param newLeft the new left son of this node. */ public void setLeft(final BinaryTreeNode<T> newLeft) { left = newLeft; } /** @return the right son of this node. */ public BinaryTreeNode<T> getRight() { return right; } /** @param newRight the new right son of this node. */ public void setRight(final BinaryTreeNode<T> newRight) { right = newRight; } } /** * Show a path from root to a give node. * @param path the qualified path from root to leaf. */ private void showPath(final Stack<BinaryTreeNode<Integer>> path) { // Print the head. System.out.print("A path is found:"); // Print each node with a leading space. for (BinaryTreeNode<Integer> node : path) { System.out.print(" "); System.out.print(node.getPos()); } System.out.println(); return; } /** * Show all paths in the tree from the root, whose sum is equal to * a given value. * @param root the root node of current (sub)tree. * @param preSum the sum of nodes in the previous path. * @param target the target value of sum of wanted paths. * @param path the nodes in the previous path from root of whole tree to here. */ public final void showPathInTree(final BinaryTreeNode<Integer> root, final int preSum, final int target, final Stack<BinaryTreeNode<Integer>> path) { assert root != null; path.push(root); if (root.getLeft() == null && root.getRight() == null) { // This is a leaf node. if (preSum + root.getValue() == target) { // This is a qualified path. showPath(path); } } else if (root.getLeft() == null) { showPathInTree(root.getRight(), preSum + root.getValue(), target, path); } else if (root.getRight() == null) { showPathInTree(root.getLeft(), preSum + root.getValue(), target, path); } else { // If both left son and right son exist, access the one with smaller // position index firstly. if (root.getLeft().getPos() <= root.getRight().getPos()) { showPathInTree(root.getLeft(), preSum + root.getValue(), target, path); showPathInTree(root.getRight(), preSum + root.getValue(), target, path); } else { showPathInTree(root.getRight(), preSum + root.getValue(), target, path); showPathInTree(root.getLeft(), preSum + root.getValue(), target, path); } } path.pop(); return; } /** * Stub for test. * @param args the command line argument. * @throws IOException when input gets error. */ @SuppressWarnings("unchecked") public static void main(final String[] args) throws IOException { StreamTokenizer st = new StreamTokenizer(new BufferedReader( new InputStreamReader(System.in))); BinaryTreeNode<Integer>[] tree = null; Stack<BinaryTreeNode<Integer>> path = new Stack<BinaryTreeNode<Integer>>(); int treeSize = 0, target = 0; PathInTree finder = new PathInTree(); while (st.nextToken() != StreamTokenizer.TT_EOF) { treeSize = (int) st.nval; st.nextToken(); target = (int) st.nval; if (treeSize == 0) { System.out.println("result:"); continue; } path.clear(); // The first item is not used. tree = (BinaryTreeNode<Integer>[]) new BinaryTreeNode[treeSize+1]; // Create the nodes. for (int i = 1; i < tree.length; ++i) { tree[i] = new BinaryTreeNode<Integer>(); } // Read the nodes' value and son(s). for (int i = 1; i < tree.length; ++i) { st.nextToken(); tree[i].setValue((int) st.nval); tree[i].setPos(i); st.nextToken(); if (((int) st.nval) != -1) { tree[i].setLeft(tree[((int) st.nval)]); } st.nextToken(); if (((int) st.nval) != -1) { tree[i].setRight(tree[((int) st.nval)]); } } // Find the paths and show. System.out.println("result:"); finder.showPathInTree(tree[1], 0, target, path); } } } |