The question is that we need to invert a binary tree by a given string.Continue reading
Monthly Archives: July 2019
Flatten a Multilevel Doubly Linked List
You are given a doubly linked list which in addition to the next and previous pointers, it could have a child pointer, which may or may not point to a separate doubly linked list. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure, as shown in the example below.
Flatten the list so that all the nodes appear in a single-level, doubly linked list. You are given the head of the first level of the list.
""" # Definition for a Node. class Node: def __init__(self, val, prev, next, child): self.val = val self.prev = prev self.next = next self.child = child """ class Solution: def flatten(self, head: 'Node') -> 'Node': if not head: return None stack = list() cur = head while cur: if cur.child: if cur.next: stack += [cur.next] cur.next = cur.child cur.next.prev = cur cur.child = None if not cur.next and stack: temp = stack.pop() cur.next = temp temp.prev = cur cur = cur.next return head
Flatten Binary Tree to Linked List
Given a binary tree, flatten it to a linked list in-place.
For example, given the following tree:
/ \ \
3 4 6
The flattened tree should look like:
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def flatten(self, root: TreeNode) -> None: """ Do not return anything, modify root in-place instead. """ node, stack = root,  while node: if node.right: stack.append(node.right) node.right = node.left node.left = None if not node.right and stack: temp = stack.pop() node.right = temp node = node.right
Reverse Linked List
Reverse a singly linked list.
Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULL
A linked list can be reversed either iteratively or recursively. Could you implement both?
As you can seen that recursion implementation is pretty easy to achieve, but iteratively achievement might not. Above are two implementations.
# iteratively class Solution(object): def reverseList(self, head): """ :type head: ListNode :rtype: ListNode """ if not head: return None pionner = head while pionner.next: old_head = head head = pionner.next pionner.next = pionner.next.next head.next = old_head return head
Given a list of daily temperatures
T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put
For example, given the list of temperatures
T = [73, 74, 75, 71, 69, 72, 76, 73], your output should be
[1, 1, 4, 2, 1, 1, 0, 0].
Note: The length of
temperatures will be in the range
[1, 30000]. Each temperature will be an integer in the range
This quiz is a classical application of the stack data structure. Here we can store indexes of each element which is waiting a bigger element in a stack, and calculate the difference between the current index and stored indexes when the current element is bigger than previous elements. The while loop part is really elegant and tricky, in which judging whether the stack is empty and comparing elements.
class Solution: def dailyTemperatures(self, T: List[int]) -> List[int]: ans =  * len(T) stk = list() for c_index, value in enumerate(T): while stk and T[stk[-1]] < value: p_index = stk.pop() ans[p_index] = c_index - p_index stk.append(c_index) return ans