Solution to Convert Binary Search Tree from Jobdu

24 Aug

Question (in Chinese):

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.

The solution is:

Leave a Reply

Your email address will not be published. Required fields are marked *