700289. Linked List to Binary Tree
Linked List to Binary Tree
Slug: make-binary-tree
Difficulty: Medium
Id: 700289
Topic Tags: Tree, Data Structures, Linked List, Queue
Company Tags: Amazon
Summary
Given a singly linked list and its length, construct the corresponding binary tree. The linked list nodes contain integer values representing the node values in the binary tree. This problem involves converting a linear data structure (linked list) to a non-linear data structure (binary tree).
Detailed Explanation
To convert the linked list into a binary tree, we can use a level-order traversal approach, where we visit each node in the order of its level and construct the corresponding nodes in the binary tree. We start by creating the root node with the middle value from the linked list.
Step-by-step breakdown:
- Initialize an empty queue to store nodes for the binary tree.
- Calculate the length of the linked list and find the middle element (if the length is odd, this will be the root node).
- Create a new node in the binary tree with the value from the middle element and enqueue it.
- Dequeue the first node from the queue and create its left child by taking the value from the next node in the linked list. If there are no more nodes in the linked list, set the left child to null. Enqueue this new left child.
- Repeat steps 3-4 for the right child of the current node.
- Continue these steps until all nodes have been visited and the binary tree is constructed.
Time complexity: O(n), where n is the length of the linked list, since we visit each node once.
Space complexity: O(n), as in the worst case, the queue can store up to n nodes.
Optimized Solutions
Java
public class LinkedListToBinaryTree {
public static Node binaryTreeFromLinkedList(Node head) {
if (head == null) return null;
Queue<Node> queue = new LinkedList<>();
int length = 0;
Node current = head;
while (current != null) {
length++;
current = current.next;
}
current = head;
for (int i = 0; i < length / 2; i++) {
Node leftChild = new Node(current.val);
queue.add(leftChild);
if (current.next != null) {
leftChild.next = new Node(current.next.val);
queue.add(leftChild.next);
}
current = current.next;
}
return head;
}
}