Question (in Chinese): http://ac.jobdu.com/problem.php?pid=1503
Question Name: Convert Binary Search Tree
Question Description: Given a binary search tree, convert it to a sorted and double-linked list. You cannot create any new node. But the pointers in each node could be modified.
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 N lines contains one test case in each line. Each test case is a list of integers, as the pre-order traversal result of the to-convert binary search tree. 0 means the corresponding left/right subtree does not exist.
Output: For each test case, print out the content from head node to the end in the converted list.
1 2 3 4 5 | Input: 1 2 1 0 0 3 0 0 Output: 1 2 3 |
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 | /*---------------------------------------------------------------- * Author: Sheng Yu codesays.com * Written: 08/23/2014 * Last updated: 08/23/2014 * * Filename: ConvertBinarySearchTree.java * Compilation: javac ConvertBinarySearchTree.java * Execution: java ConvertBinarySearchTree * 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; import java.util.Stack; /** * The utility to convert a binary search tree to double-linked list. * @author Sheng Yu codesays.com */ public class ConvertBinarySearchTree { /** * 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; /** @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; } } /** * 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 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)); return root; } /** * Covert the given binary search tree into double-linked list in place. * The left son pointer becomes the link to the previous node. * The right son pointer becomes the link to the next node. * @param root the root node of a binary search tree. * @return the head node of the converted double-linked list. */ @SuppressWarnings("rawtypes") public Node convert2List(Node root) { // Do a in-order iterative traversal, and we can modify the nodes // in place during the traversal. Node previous = null; Node current = root; Stack<Node> nodes = new Stack<Node>(); // Do the in-ordr traversal. while (current != null || !nodes.empty()) { while (current != null) { nodes.add(current); current = current.getLeft(); } current = nodes.pop(); // Modify the links to convert this binary search tree to list. if (previous != null) { previous.setRight(current); current.setLeft(previous); } else { current.setLeft(null); } previous = current; current = current.getRight(); } // End this double-linked list. previous.setRight(null); // Travel backward to find the head node of the list. current = previous; while (current.getLeft() != null) current = current.getLeft(); return current; } /** * Show the content of the given double-linked or single-linked list. * @param head the head node of the list to show. */ @SuppressWarnings("rawtypes") public void showList(Node head) { StringBuilder sb = new StringBuilder(); // Print each node with one taiig space. Node current = head; while (current != null) { sb.append(current.getValue()); sb.append(" "); current = current.getRight(); } // Show the content. System.out.println(sb); return; } /** * Stub for test. * @param args the command line arguments * @throws IOException when input get 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> head = null; ConvertBinarySearchTree utility = new ConvertBinarySearchTree(); 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 = utility.buildTree(input); head = (Node<Integer>) utility.convert2List(root); utility.showList(head); } } } |