50182. Two Lists to Tree

Task Description

This task is to build a tree from two linked lists. Every node of the two linked lists has a distinct integer value and two pointers, left and right. Initially, the left pointer of a node points to the next node in the linked list, and the right pointer is NULL.

Now we define how to split a linked list of $n$ nodes into two halves. If $n$ is even, then the first half has the first $n/2$ nodes of the list, and the second half has $n/2$ nodes of the list. If $n$ is odd, then the first half has of the first $(n+1)/2$ node of the list, and the second half has $(n-1)/2$ nodes of the list.

Here is a recursive definition to build a tree $T$ from two linked lists $L$ and $R$.

1. If both $L$ and $R$ are not NULL, then we compare the value of the head of two linked lists, and the smaller one is the root of $T$. We then recursively build the left subtree of $T$ from the two first halves of the remaining $L$ and $R$, and recursively build the right subtree from the two second halves of remaining $L$ and $R$.
2. If either $L$ or $R$ is NULL, then the tree is the non-NULL one of $L$ or $R$. That is, all the nodes in the tree are in the left subtree.
3. If both $L$ and $R$ are NULL, the tree is NULL.

Note that you can only use the list nodes given to you, and you cannot allocate any large amount of memory.

Please refer to the following figure for an illustration.

Tree

You have to do it in a function, BuildTree. The arguments of BuildTree are two pointers, and each of them points to a linked list. The return value is the root of the tree. The following is BuildTree.h file.

typedef struct Node
{
          int val;
          struct Node *left, *right;
}Node;
Node* BuildTree(Node* list1, Node* list2);

You can test your function with this main function.

#include <stdio.h>
#include "BuildTree.h"
#define MAXN 100
 
void tree_print(Node* root){
          if(root == NULL) return;
          printf("%d ", root->val);
          tree_print(root->left);
          tree_print(root->right);
}
 
int main()
{
          int i, n, m, num;
          Node l1[MAXN], l2[MAXN];
 
          scanf("%d%d", &n, &m);
          for(i = 0; i < n; i++){
                   scanf("%d", &num);
                   l1[i].val = num;
                   l1[i].left = &l1[i+1];
                   l1[i].right = NULL;
          }
          l1[n-1].left = NULL;
          Node *root1 = &l1[0];
          for(i = 0; i < m; i++){
                   scanf("%d", &num);
                   l2[i].val = num;
                   l2[i].left = &l2[i+1];
                   l2[i].right = NULL;
          }
          l2[m-1].left = NULL;
          Node *root2 = &l2[0];
 
          Node *ans = BuildTree(root1, root2);
          tree_print(ans);
          printf("\n");
 
          return 0;
}

Input Format

The first line has two integers, n and m. They are the lengths of two linked list. The second line has n integers, which are the values of the first linked list. The third line has m integers, which are the values of the second linked list.

Output Format

Output the preorder of the tree.

Sample Input 1

3 4
4 7 0
6 9 5 3

Sample Output 1

4 6 7 9 0 5 3

Sample Input 2

3 7
8 11 1
4 5 3 9 13 2 7

Sample Output 2

4 5 3 8 9 11 1 13 2 7