Microsoft Interview Question
SDE-2sCountry: United States
Interview Type: In-Person
// Time Complexity O(n)
static Node constructTree(int[] pre, int size) {
Node root = new Node(pre[0]);
Stack<Node> stack = new Stack<Node>();
stack.push(root);
for (int index = 1; index < size; index++) {
Node temp = null;
while (!stack.isEmpty() && pre[index] > stack.peek().data) {
temp = stack.pop();
}
if (null != temp) {
temp.right = new Node(pre[index]);
stack.push(temp.right);
} else {
temp = stack.peek();
temp.left = new Node(pre[index]);
stack.push(temp.left);
}
}
return root;
}
// Time Complexity O(n)
static Node constructTree(int[] pre, int size) {
Node root = new Node(pre[0]);
Stack<Node> stack = new Stack<Node>();
stack.push(root);
for (int index = 1; index < size; index++) {
Node temp = null;
while (!stack.isEmpty() && pre[index] > stack.peek().data) {
temp = stack.pop();
}
if (null != temp) {
temp.right = new Node(pre[index]);
stack.push(temp.right);
} else {
temp = stack.peek();
temp.left = new Node(pre[index]);
stack.push(temp.left);
}
}
return root;
}
public static TreeNode getTreeFromPreorder(int[] nums){
Deque<TreeNode> deque = new ArrayDeque<>();
if(nums==null || nums.length<1){
return null;
}
TreeNode root = new TreeNode(nums[0]);
deque.offer(root);
for(int i=1;i<nums.length;i++){
TreeNode node = new TreeNode(nums[i]);
TreeNode temp = null;
while(!deque.isEmpty()&&deque.peekLast().val<node.val){
temp = deque.pollLast();
}
if(temp!=null){
temp.right = node;
deque.offer(node);
}else{
deque.peekLast().left = node;
deque.offer(node);
}
}
return root;
}
public static TreeNode getTreeFromPreorder(int[] nums){
Deque<TreeNode> deque = new ArrayDeque<>();
if(nums==null || nums.length<1){
return null;
}
TreeNode root = new TreeNode(nums[0]);
deque.offer(root);
for(int i=1;i<nums.length;i++){
TreeNode node = new TreeNode(nums[i]);
TreeNode temp = null;
while(!deque.isEmpty()&&deque.peekLast().val<node.val){
temp = deque.pollLast();
}
if(temp!=null){
temp.right = node;
deque.offer(node);
}else{
deque.peekLast().left = node;
deque.offer(node);
}
}
return root;
}
- koustav.adorable September 04, 2017