Construct Binary Search Tree from Preorder Traversal
Problem is here: https://leetcode.com/problems/construct-binary-search-tree-from-preorder-traversal/
This is a relatively simple problem, although labeled as Medium. The definition of a binary search tree is even given in the problem description. A recursive solution does the trick: add the first node, then call recursively for the left by creating a sub-array with the smaller elements, and similar to the right. That should do it. Conversion of linked-lists to arrays in C# is not the most efficient operation, hence the execution time slows down a bit. Code is below, cheers, ACC.
Return the root node of a binary search tree that matches the given
preorder traversal.
(Recall that a binary search tree is a binary tree where for every node, any descendant of
node.left has a value < node.val, and any descendant of node.right has a value > node.val. Also recall that a preorder traversal displays the value of the node first, then traverses node.left, then traverses node.right.)
Example 1:
Input: [8,5,1,7,10,12] Output: [8,5,10,1,7,null,12]
Note:
1 <= preorder.length <= 100- The values of
preorderare distinct.
This is a relatively simple problem, although labeled as Medium. The definition of a binary search tree is even given in the problem description. A recursive solution does the trick: add the first node, then call recursively for the left by creating a sub-array with the smaller elements, and similar to the right. That should do it. Conversion of linked-lists to arrays in C# is not the most efficient operation, hence the execution time slows down a bit. Code is below, cheers, ACC.
public class Solution
{
public TreeNode BstFromPreorder(int[] preorder)
{
if (preorder == null || preorder.Length == 0) return null;
TreeNode tree = new TreeNode(preorder[0]);
LinkedList left = new LinkedList();
int i = 1;
for (; i < preorder.Length && preorder[i] < preorder[0]; i++)
{
left.AddLast(preorder[i]);
}
LinkedList right = new LinkedList();
for (; i < preorder.Length; i++)
{
right.AddLast(preorder[i]);
}
tree.left = BstFromPreorder(left.ToArray());
tree.right = BstFromPreorder(right.ToArray());
return tree;
}
}
Comments
Neat! I've used a very similar approach, which runs a lot faster on any non-C# languages it seems like (Python code below runs in 36s and beats 100% of other submissions) :) Seriously speaking though, I think the reason for the slow runtime of your submission is usage of LinkedList - I bet just by replacing it with ArrayList you'd get a significantly better performance. LinkedList has a terrible effect on caches (non-contiguous memory) and uses more memory (thanks to pointers). LinkedLists are so bad that many advocate for their removal from standard libraries :)
Reply Deleteclass Solution:
def bstFromPreorder(self, preorder: List[int]) -> TreeNode:
if not preorder:
return None
root = TreeNode(preorder[0])
first_right_child_idx = len(preorder)
for idx, node in enumerate(preorder):
if node > root.val:
first_right_child_idx = idx
break
root.left = self.bstFromPreorder(preorder[1:first_right_child_idx])
root.right = self.bstFromPreorder(preorder[first_right_child_idx:])
return root
https://gist.github.com/ttsugriy/849ae99d210ff775a0b094ec03beb361
Post a Comment
[γγ¬γΌγ ]