Leetcode Solutions
Contents
Leetcode Solutions¶
33. Search in Rotated Sorted Array¶
def search(nums, target):
lo, hi = 0, len(nums)-1
while lo <= hi:
mid = (lo+hi)//2
if nums[mid] == target:
return mid
elif nums[hi] > nums[mid]:
if nums[mid] < target <= nums[hi]:
lo = mid+1
else:
hi = mid-1
else:
if nums[lo] <= target < nums[mid]:
hi = mid-1
else:
lo = mid+1
return -1
34. Find First and Last Position of Element in Sorted Array¶
def searchRange(self, nums, target):
lo, hi = 0, len(nums)-1
def first_position(lo, hi, target):
while lo<=hi:
mid = (lo+hi)//2
if nums[mid] == target:
if mid-1>=0 and nums[mid-1] == target:
hi = mid-1
else:
return mid
elif nums[mid] > target:
hi = mid-1
elif nums[mid] < target:
lo = mid+1
return -1
def last_position(lo, hi, target):
while lo<=hi:
mid = (lo+hi)//2
if nums[mid] == target:
if mid+1<=hi and nums[mid+1] == target:
lo = mid+1
else:
return mid
elif nums[mid] > target:
hi = mid-1
elif nums[mid] < target:
lo = mid+1
return -1
return([first_position(lo, hi, target), last_position(lo, hi, target)])
94. Binary Tree Inorder Traversal¶
# Method 1: Recursion 递归
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if root is None:
return []
return (self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right))
104. Maximum Depth of Binary Tree¶
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def maxDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if root is None:
return 0
return 1+max(self.maxDepth(root.left),self.maxDepth(root.right))
111. Minimum Depth of Binary Tree¶
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def minDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if root is None:
return 0
elif root.left is None and root.right is not None:
return 1+self.minDepth(root.right)
elif root.right is None and root.left is not None:
return 1+self.minDepth(root.left)
return 1+min(self.minDepth(root.left),self.minDepth(root.right))
144. Binary Tree Preorder Traversal¶
# Method 1: Recursion 递归
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def preorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if root is None:
return []
return ([root.val] + self.preorderTraversal(root.left) + self.preorderTraversal(root.right))
145. Binary Tree Postorder Traversal¶
# Method 1: Recursion 递归
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def postorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if root is None:
return []
return (self.postorderTraversal(root.left) + self.postorderTraversal(root.right) + [root.val])
543. Diameter of Binary Tree¶
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def diameterOfBinaryTree(self, root):
"""
:type root: TreeNode
:rtype: int
"""
def depth(root):
if root is None:
return 0
return 1+max(depth(root.left),depth(root.right))
if root is None:
return 0
return max(depth(root.left)+depth(root.right), self.diameterOfBinaryTree(root.left), self.diameterOfBinaryTree(root.right))
704. Binary Search¶
def search(self, nums, target):
lo, hi = 0, len(nums)-1
while lo <= hi:
mid = (lo+hi)//2
if nums[mid] == target:
if mid-1>=0 and nums[mid-1]==target:
hi = mid-1
else:
return mid
elif nums[mid] < target:
lo = mid+1
elif nums[mid] > target:
hi = mid-1
return -1
*958. Check Completeness of a Binary Tree¶
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def isCompleteTree(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
nodes = [(root,1)]
i = 0
while i < len(nodes):
node, v = nodes[i]
if node is not None:
nodes.append((node.left, 2*v))
nodes.append((node.right, 2*v+1))
i+=1
return nodes[-1][1] == len(nodes)