Given a binary tree, find its minimum depth. The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node. Note: A leaf is a node with no children. Example: Given binary tree [3,9,20,null,null,15,7],
Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid operators are +, -, *, /. Each operand may be an integer or another expression. Note: Division between two integers should truncate toward zero. The given RPN expression is always valid. That means the expression would always evaluate to a result and there won’t be any divide by zero operation.
# Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None
class(object): defsortList(self, head): """ :type head: ListNode :rtype: ListNode """ ifnot head: returnNone else: ifnot head.next: return head else: slow, fast = head, head.next while fast and fast.next: slow = slow.next fast = fast.next.next h1, h2 = head, slow.next slow.next = None left = self.sortList(h1) right = self.sortList(h2) if left.val < right.val: h = left left = left.next else: h = right right = right.next p = h while left and right: if left.val < right.val: p.next = left p = p.next left = left.next else: p.next = right p = p.next right = right.next if left: p.next = left if right: p.next = right return h
Insertion Sort List
Description
Sort a linked list using insertion sort.
A graphical example of insertion sort. The partial sorted list (black) initially contains only the first element in the list. With each iteration one element (red) is removed from the input data and inserted in-place into the sorted list
Algorithm of Insertion Sort:
Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list.
At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there.
# Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None
class(object): defisSortList(self, head): while head and head.next: if head.val > head.next.val: returnFalse else: head = head.next returnTrue definsertionSortList(self, head): """ :type head: ListNode :rtype: ListNode """ if self.isSortList(head): return head else: dummy, tail, cur = ListNode(float('inf')), head, head.next dummy.next = head while cur: pre = dummy while pre.next and cur.val > pre.next.val: pre = pre.next if pre == tail: tail, cur = cur, cur.next else: tail.next = cur.next cur.next, pre.next = pre.next, cur cur = tail.next return dummy.next
Binary Tree Postorder Traversal
Description
Given a binary tree, return the postorder traversal of its nodes’ values.
Example:
1 2 3 4 5 6 7 8
Input: [1,null,2,3] 1 2 / 3
Output: [3,2,1]
Follow up: Recursive solution is trivial, could you do it iteratively?
# class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None
classSolution(object): defpreorderTraversal(self, root): """ :type root: TreeNode :rtype: List[int] """ self.result = [] defpreorder(root): cur, stack = root, [] while cur or stack: while cur: self.result.append(cur.val) stack.append(cur) cur = cur.left cur = stack.pop() cur = cur.right preorder(root) return self.result
Reorder List
Description
Given a singly linked list L: L0→L1→…→Ln-1→Ln, reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→… You may not modify the values in the list’s nodes, only nodes itself may be changed.
# Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None
classSolution(object): defreorderList(self, head): """ :type head: ListNode :rtype: void Do not return anything, modify head in-place instead. """ if head and head.next: fast, slow, pre = head, head, None while fast and fast.next: fast, slow, pre = fast.next.next, slow.next, slow pre.next, pre = None, None cur = slow while cur != None: cur.next, pre, cur = pre, cur, cur.next l1, l2 = head, pre dummy = ListNode(0) cur = dummy while l1 and l2: cur.next, cur, l1 = l1, l1, l1.next cur.next, cur, l2 = l2, l2, l2.next head = dummy.next
Linked List Cycle II
Description
Given a linked list, return the node where the cycle begins. If there is no cycle, return null. Note: Do not modify the linked list. Follow up: Can you solve it without using extra space?
# Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None
classSolution(object): defdetectCycle(self, head): """ :type head: ListNode :rtype: ListNode """ fast, slow = head, head while fast and fast.next: fast, slow = fast.next.next, slow.next if fast == slow: fast = head while fast != slow: fast, slow = fast.next, slow.next return fast returnNone
Linked List Cycle
Description
Given a linked list, determine if it has a cycle in it. Follow up: Can you solve it without using extra space?
# Definition for singly-linked list.# class ListNode(object):# def __init__(self, x):# self.val = x# self.next = NoneclassSolution(object):defhasCycle(self, head):""" :type head: ListNode :rtype: bool """
fast, slow = head, head
while fast and fast.next:
fast, slow = fast.next.next, slow.next
if fast == slow:
returnTruereturnFalse
近期评论