Question (in Chinese): http://ac.jobdu.com/problem.php?pid=1520
Question Name: Substructure In Tree
Question Description: Give two binary tree, check whether the latter one is a substructure of the first one.
Input: the input might contain multiple test cases. Inside each test case, the first line includes two interger N and M (0 <= N, M <= 1000), saying the size of the first and second binary tree respectively. The second line includes N integers, as the value of each node in the first tree (the first node is the root node). Then the following N lines have three different formations. The i(th) line is
1. Contains only one integer: 0, means the (i)th node has no child; OR
2. Contains two integers: 1 and another integer LS, means the (i)th node only have (LS)th node as its left son; OR
3. Contains three integers: 2 LS RS, means the (i)th node has (LS)th node as its left son, and (RS)th node as its right son.
After that, the following (M+1) lines are the information in the same formation about the second tree..
PS: both the line NO. and the nodes are 1-based index.
Output: “NO” if the second tree is not a substructure of the first one. Otherwise, print out “YES”. An empty tree is not a substructure of any tree.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | Input: 7 3 8 8 7 9 2 4 7 2 2 3 2 4 5 2 6 7 8 9 2 2 2 3 1 1 2 3 Output: YES NO Appendix: the corresponding tree for the first input 8 8 / / 8 7 and 9 2 / 9 2 / 4 7 |
The following is a recursive solution.
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 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 | /*---------------------------------------------------------------- * Author: Sheng Yu codesays.com * Written: 08/08/2014 * Last updated: 08/08/2014 * * Filename: SubstructureInTree.java * Compilation: javac SubstructureInTree.java * Execution: java SubstructureInTree * JDK Used: 1.7 *----------------------------------------------------------------*/ import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.StreamTokenizer; /** * This class include a definition of binary tree, and the function to * check whether a tree is a substructure of another. * @author Sheng Yu codesays.com */ public class SubstructureInTree { /** * 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 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 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; } } /** * Test whether the second is a substructure of the first, starting at the * current first node. * @param first the first binary tree, not null. * @param second the second binary tree, not null. * @return whether the second is a substructure of first. */ private boolean isSubstructureHelper(final BinaryTreeNode<Integer> first, final BinaryTreeNode<Integer> second) { // Test current node. if (first.getValue() != second.getValue()) { return false; } // Test left sub-trees if exist. if (first.getLeft() != null && second.getLeft() != null) { if (!isSubstructureHelper(first.getLeft(), second.getLeft())) { return false; } } else if (first.getLeft() == null && second.getLeft() != null) { return false; } // Test right sub-trees if exist. if (first.getRight() != null && second.getRight() != null) { if (!isSubstructureHelper(first.getRight(), second.getRight())) { return false; } } else if (first.getRight() == null && second.getRight() != null) { return false; } return true; } /** * To check whether the second binary tree is a substructure of the * first one. * @param first the first binary tree * @param second the second binary tree * @return whether the tree second is a substructure of first. */ public final boolean isSubstructure(final BinaryTreeNode<Integer> first, final BinaryTreeNode<Integer> second) { // If second is empty, it is not the substructure of anyone. // For this test stub, second will always be non-null. if (second == null) { return false; } // If second is not empty, but first is, second is not a substructure. if (first == null) { return false; } // Second is a substructure, starting here. if (first.getValue() == second.getValue() && isSubstructureHelper(first, second)) { return true; } // Try to find other places, second might be a substructure. return isSubstructure(first.getLeft(), second) || isSubstructure(first.getRight(), second); } /** * Stub for test. * @param args the command line arguments. * @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>[] first = null, second = null; int sonCount = 0; SubstructureInTree checker = new SubstructureInTree(); while (st.nextToken() != StreamTokenizer.TT_EOF) { // Get the size of the two trees. first = null; second = null; if ((int) st.nval > 0) { first = (BinaryTreeNode<Integer>[]) new BinaryTreeNode[(int) st.nval]; } st.nextToken(); if ((int) st.nval > 0) { second = (BinaryTreeNode<Integer>[]) new BinaryTreeNode[(int) st.nval]; } // Get the content of the two trees. if (first != null) { for (int i = 0; i < first.length; ++i) { st.nextToken(); first[i] = new BinaryTreeNode<Integer>(); first[i].setValue((int) st.nval); } for (int i = 0; i < first.length; ++i) { st.nextToken(); sonCount = (int) st.nval; if (sonCount >= 1) { // Has left son. st.nextToken(); first[i].setLeft(first[((int) st.nval) - 1]); } if (sonCount == 2) { // Has right son. st.nextToken(); first[i].setRight(first[((int) st.nval) - 1]); } } } if (second != null) { for (int i = 0; i < second.length; ++i) { st.nextToken(); second[i] = new BinaryTreeNode<Integer>(); second[i].setValue((int) st.nval); } for (int i = 0; i < second.length; ++i) { st.nextToken(); sonCount = (int) st.nval; if (sonCount >= 1) { // Has left son. st.nextToken(); second[i].setLeft(second[((int) st.nval) - 1]); } if (sonCount == 2) { // Has right son. st.nextToken(); second[i].setRight(second[((int) st.nval) - 1]); } } } // Check whether the second tree is a substructure of the first one. if (first == null || second == null) { System.out.println("NO"); } else if (checker.isSubstructure(first[0], second[0])) { System.out.println("YES"); } else { System.out.println("NO"); } } } } |