Question (in Chinese): http://ac.jobdu.com/problem.php?pid=1367
Question Name: Sequence Of BST
Question Description: Give an array, check whether it is possble to be the post-order traversal result on some binary search tree.
Input: the input might contain multiple test cases. Inside each test case, the first line includes one interger N (0 <= N <= 10000), saying the size of the array. The second line includes N integers, as the value of the array.
Output: “Yes” if the array is the post-order result of some BST. Otherwise, print “No”.
1 2 3 4 5 6 7 8 | Input: 7 5 7 6 9 11 10 8 4 7 4 6 5 Output: Yes No |
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 | /*---------------------------------------------------------------- * Author: Sheng Yu codesays.com * Written: 08/12/2014 * Last updated: 08/12/2014 * * Filename: SequenceOfBST.java * Compilation: javac SequenceOfBST.java * Execution: java SequenceOfBST * JDK Used: 1.7 *----------------------------------------------------------------*/ import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.StreamTokenizer; /** * A utility class to determine whether the array could be the result * of post order traversal on any Binary Search Tree. * @author Sheng Yu codesays.com */ public class SequenceOfBST { /** * Checke whether the given array is possible to be the result of * post order traversal on any BST. * @param toCheck the array to check. * @return true if the given array could be the post-order traversal * of some BST. false otherwise. */ public final boolean isValidPostOrderTraversal(final int[] toCheck) { return isValidPostOrderTraversal(toCheck, 0, toCheck.length - 1); } /** * Checke whether the given array is possible to be the result of * post order traversal on any BST. * @param toCheck the array to check. * @param beginPos the begin (inclusive) position of the array to check. * @param endPos the end (inclusive) position of the array to check. * @return true if the given array could be the post-order traversal * of some BST. false otherwise. */ public final boolean isValidPostOrderTraversal(final int[] toCheck, final int beginPos, final int endPos) { if (beginPos >= endPos) { // Empty (sub)tree return true; } // Chech the subtree with toCheck[endPos] being the root. int current = beginPos; int endOfLeftSubtree = -1; int root = toCheck[endPos]; // root of this sub-tree. while (toCheck[current] < root) { ++current; } endOfLeftSubtree = current - 1; while (current < endPos) { if (toCheck[current] < root) { return false; } ++current; } // Check the left sub-tree. if (endOfLeftSubtree > beginPos && !isValidPostOrderTraversal(toCheck, beginPos, endOfLeftSubtree)) { return false; } // Check the right sub-tree. if (endOfLeftSubtree + 1 < endPos - 1 && !isValidPostOrderTraversal(toCheck, endOfLeftSubtree + 1, endPos - 1)) { return false; } return true; } /** * Stub for test. * @param args the command line arguments. * @throws IOException when input gets error. */ public static void main(final String[] args) throws IOException { StreamTokenizer st = new StreamTokenizer(new BufferedReader( new InputStreamReader(System.in))); int size = 0; int[] toCheck = null; SequenceOfBST checker = new SequenceOfBST(); while (st.nextToken() != StreamTokenizer.TT_EOF) { // Get the size of the array. size = (int) st.nval; toCheck = new int[size]; // Get the array content. while (size-- > 0) { st.nextToken(); toCheck[toCheck.length - size - 1] = (int) st.nval; } // Check whether the array is possible to be the result of post- // order traversal on any BST. if (checker.isValidPostOrderTraversal(toCheck)) { System.out.println("Yes"); } else { System.out.println("No"); } } } } |