Question (in Chinese): http://ac.jobdu.com/problem.php?pid=1350
Question Name: Tree Depth
Question Description: compute the depth of a binary tree.
Input: the input might contain multiple test cases. Inside each test case, the first line includes one integers N (1 <= N <= 10), saying the number of nodes in the binary tree. The following N lines indicate the sons of the nodes (1-based index, and the first node is the root node). i(th) line contains two integers X and Y. And the X(th) node is the left son of i(th) node, and Y(th) the right son. X/Y is -1, if there is no such son.
Output: print the height of the tree.
1 2 3 4 5 6 7 | Input: 3 2 3 -1 -1 -1 -1 Output: 2 |
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 | /*---------------------------------------------------------------- * Author: Sheng Yu - codesays.com * Written: 09/07/2014 * Last updated: 09/07/2014 * * Filename: TreeDepth.java * Compilation: javac TreeDepth.java * Execution: java TreeDepth * JDK Used: 1.7 *----------------------------------------------------------------*/ import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.StreamTokenizer; /** * An utility to find the height of a binary tree. * @author Sheng Yu codesays.com */ public class TreeDepth { /** * The definition of node in binary search tree. * @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; /** @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/previous node of this node. */ public Node<T> getLeft() { return left; } /** @param newLeft the new left son/previous node of this node. */ public void setLeft(Node<T> newLeft) { left = newLeft; } /** @return the right son/next node of this node. */ public Node<T> getRight() { return right; } /** @param newRight the new right son/next node of this node. */ public void setRight(Node<T> newRight) { right = newRight; } /** * Compute the height of the subtree with current node being root. * @return the height of current subtree. */ public int height() { return height(this); } /** * Compute the height of the subtree with root. * @return the height of current subtree. */ @SuppressWarnings("rawtypes") public int height(Node root) { if (root == null) return 0; else return Math.max(height(root.getLeft()), height(root.getRight()) ) + 1; } } /** * Stub for test. * @param args the command line arguments. * @throws IOException when input gets error. */ @SuppressWarnings("rawtypes") public static void main(String[] args) throws IOException { StreamTokenizer st = new StreamTokenizer(new BufferedReader( new InputStreamReader(System.in))); while (st.nextToken() != StreamTokenizer.TT_EOF) { // Create the nodes. Node[] nodes = new Node[(int) st.nval]; for (int i = 0; i < nodes.length; ++i) nodes[i] = new Node(); // Create the son-relationship for (int line = 0; line < nodes.length; ++line) { st.nextToken(); if (((int) st.nval) != -1 ) { nodes[line].setLeft(nodes[((int) st.nval) - 1]); } st.nextToken(); if (((int) st.nval) != -1 ) { nodes[line].setRight(nodes[((int) st.nval) - 1]); } } // Compute the height System.out.println(nodes[0].height()); } } } |