Question (in Chinese): http://ac.jobdu.com/problem.php?pid=1509
Question Name: Lowest Common Ancestor
Question Description: Find the lowest common ancestor of two nodes in a binary tree.
Input: the input might contain multiple test cases. Globally the first line includes one interger N (0 <= N <= 1000). N is the number of test cases. The following 2*N lines contains one test case in each two lines. The first line of each test case is a list of integers, as the pre-order traversal result of a binary tree. 0 means the corresponding left/right subtree does not exist. The second line is two integers, as the value of two nodes (may not exist).
Output: print the value of the lowest common ancestor, if exist. Otherwise, print “My God”.
1 2 3 4 5 6 7 8 9 | Input: 2 1 2 4 6 0 0 7 0 0 5 8 0 0 9 0 0 3 0 0 6 8 1 2 4 6 0 0 7 0 0 5 8 0 0 9 0 0 3 0 0 6 12 Output: 2 My God |
The solution is quite complicated if we need a really good performance. But here we are using a simple 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 | /*---------------------------------------------------------------- * Author: Sheng Yu - codesays.com * Written: 09/14/2014 * Last updated: 09/14/2014 * * Filename: LowestCommonAncestor.java * Compilation: javac LowestCommonAncestor.java * Execution: java LowestCommonAncestor * JDK Used: 1.7 *----------------------------------------------------------------*/ import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.StreamTokenizer; import java.util.LinkedList; import java.util.Queue; /** * The utility to find the lowest common ancestor of two nodes in a binary tree. * @author Sheng Yu codesays.com */ public class LowestCommonAncestor { /** * The definition of node in binary search tree or double-linked list. * @author Sheng Yu codesays.com * @param <T> the type of the value in the node. */ private static class Node<T> { /** The value of current node. */ private T value = null; /** The left of current node. */ private Node<T> left = null; /** The right son of current node. */ private Node<T> right = null; /** The father of current node. */ private Node<T> father = null; /** @return the value of this node. */ public T getValue() { return value; } /** @param newValue the new value of this node. */ public void setValue(T newValue) { value = newValue; } /** @return the left son of this node. */ public Node<T> getLeft() { return left; } /** @param newLeft the new left son of this node. */ public void setLeft(Node<T> newLeft) { left = newLeft; } /** @return the right son of this node. */ public Node<T> getRight() { return right; } /** @param newRight the new right son of this node. */ public void setRight(Node<T> newRight) { right = newRight; } /** @return the father of this node. */ public Node<T> getFather() { return father; } /** @param newFather the father of this node. */ public void setFather(Node<T> newFather) { father = newFather; } } /** * Build a binary search tree from a queue. * @param input the in-order traversal result of the binary search tree. * @return the root node of the built tree. */ public static Node<Integer> buildTree(Queue<Integer> input) { int current = input.remove(); if (current == 0) return null; Node<Integer> root = new Node<Integer>(); root.setValue(current); root.setLeft(buildTree(input)); root.setRight(buildTree(input)); if (root.getLeft() != null) root.getLeft().setFather(root); if (root.getRight() != null) root.getRight().setFather(root); return root; } /** * Find the node in the tree, whose value is the given one. * @param root the root node of the tree. * @param value the value to find. * @return the wanted node, if exist. null, otherwise. */ public static Node<Integer> findNode(Node<Integer> root, int value) { Node<Integer> result = null; if (root.getValue() == value) { result = root; } else { if (root.getLeft() != null) { result = findNode(root.getLeft(), value); } if (result == null && root.getRight() != null) { result = findNode(root.getRight(), value); } } return result; } /** * Find the lowest common ancestor of the first and second nodes. * @param first the first node of the binary tree. * @param second the second node of the binary tree. * @return the lowest common ancestor of the two nodes. */ public static Node<Integer> LCA(Node<Integer> first, Node<Integer> second) { // Get the height from first node to the root. int firstLen = 0; Node<Integer> firstCurrent = first; while (firstCurrent != null) { ++firstLen; firstCurrent = firstCurrent.getFather(); } // Get the height from second node to the root. int secondlen = 0; Node<Integer> secondCurrent = second; while (secondCurrent != null) { ++secondlen; secondCurrent = secondCurrent.getFather(); } // Make sure both firstCurrent and secondCurrent have the same depth. firstCurrent = first; secondCurrent = second; while (firstLen > secondlen) { --firstLen; firstCurrent = firstCurrent.getFather(); } while (firstLen < secondlen) { --secondlen; secondCurrent = secondCurrent.getFather(); } // Find the lowest common ancestor. while (firstCurrent != secondCurrent) { firstCurrent = firstCurrent.getFather(); secondCurrent = secondCurrent.getFather(); } return firstCurrent; } /** * Stub for test. * @param args the command line arguments. * @throws IOException when input gets error. */ public static void main(String[] args) throws IOException { StreamTokenizer st = new StreamTokenizer(new BufferedReader( new InputStreamReader(System.in))); st.eolIsSignificant(true); int testCases = 0; int token = 0; Queue<Integer> input = new LinkedList<Integer>(); Node<Integer> root = null; Node<Integer> ancestor = null; st.nextToken(); testCases = (int) st.nval; token = st.nextToken(); while (testCases-- > 0) { input.clear(); // Get the input as a new test case. token = st.nextToken(); while (token != StreamTokenizer.TT_EOL && token != StreamTokenizer.TT_EOF) { input.add((int) st.nval); token = st.nextToken(); } // Build a tree from the input, convert it to a double-linked list, // and finally show the list. root = buildTree(input); st.nextToken(); Node<Integer> first = findNode(root, (int) st.nval); st.nextToken(); Node<Integer> second = findNode(root, (int) st.nval); token = st.nextToken(); // Skip the EOL. if (first != null && second != null) { ancestor = LCA(first, second); } else { ancestor = null; } if (ancestor == null) System.out.println("My God"); else System.out.println(ancestor.getValue()); } } } |