Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1...n.
For example, Given n = 3, your program should return all 5 unique BST's shown below.
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def generateTrees(self, n):
"""
:type n: int
:rtype: List[TreeNode]
"""
if n == 0: return []
return self.generate(1,n)
def generate(self, i, j):
l = []
if i > j: l.append(None)
for k in xrange(i, j+1):
left = self.generate(i,k-1)
right = self.generate(k+1,j)
for nodeleft in left:
for noderight in right:
root = TreeNode(k)
root.left = nodeleft
root.right = noderight
l.append(root)
return l
Given a string containing only digits, restore it by returning all possible valid IP address combinations.
For example: Given "25525511135",
return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)
class Solution(object):
def restoreIpAddresses(self, s):
"""
:type s: str
:rtype: List[str]
"""
res = []
for a in range(1,4):
for b in range(1,4):
for c in range(1,4):
for d in range(1,4):
if a+b+c+d == len(s):
A = int(s[0:a])
B = int(s[a:a+b])
C = int(s[a+b:a+b+c])
D = int(s[a+b+c:a+b+c+d])
if A <= 255 and B <= 255 and C <= 255 and D <= 255:
ans = str(A)+'.'+str(B)+'.'+str(C)+'.'+str(D)
if len(ans) == len(s) + 3:
res.append(ans)
return res
Given a collection of distinct numbers, return all possible permutations.
For example, [1,2,3] have the following permutations:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
class Solution(object):
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
res = []
self.dfs(nums, [], res)
return res
def dfs(self, nums, path, res):
if not nums:
res.append(path)
for i in xrange(len(nums)):
self.dfs(nums[:i]+nums[i+1:], path+[nums[i]], res)
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def sortedArrayToBST(self, nums):
"""
:type nums: List[int]
:rtype: TreeNode
"""
if not nums: return None
return self.dfs(nums, 0, len(nums)-1)
def dfs(self, num, start, end):
if start > end:
return None
if start == end:
return TreeNode(num[start])
mid = start + (end-start)/2
root = TreeNode(num[mid])
root.left = self.dfs(num, start, mid-1)
root.right = self.dfs(num, mid+1, end)
return root
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
class Solution:
# @param {ListNode} head
# @return {TreeNode}
def sortedListToBST(self, head):
if not head:
return None
if not head.next:
return TreeNode(head.val)
dummyHead = ListNode(0)
dummyHead.next = head
slow, fast = dummyHead, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
root = TreeNode(slow.next.val)
root.right = self.sortedListToBST(slow.next.next)
slow.next = None
root.left = self.sortedListToBST(head)
return root
There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
Example 1:
nums1 = [1, 3]
nums2 = [2]
The median is 2.0
Example 2:
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5
class Solution:
# @return a float
def findMedianSortedArrays(self, A, B):
l=len(A)+len(B)
return self.findKth(A,B,l//2) if l%2==1 else (self.findKth(A,B,l//2-1)+self.findKth(A,B,l//2))/2.0
def findKth(self,A,B,k):
if len(A)>len(B):
A,B=B,A
if not A:
return B[k]
if k==len(A)+len(B)-1:
return max(A[-1],B[-1])
i=len(A)//2
j=k-i
if A[i]>B[j]:
#Here I assume it is O(1) to get A[:i] and B[j:]. In python, it's not but in cpp it is.
return self.findKth(A[:i],B[j:],i) # 如果A[i] > B[j],那么必然不在B[:j]里,所以裁去B[:j]部分
else:
return self.findKth(A[i:],B[:j],j)
Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
The left subtree of a node contains only nodes with keys less than the node's key. The right subtree of a node contains only nodes with keys greater than the node's key. Both the left and right subtrees must also be binary search trees. Example 1:
2
/ \
1 3
Binary tree [2,1,3], return true. Example 2:
1
/ \
2 3
Binary tree [1,2,3], return false.
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def func(self, root, start, end):
if not root:
return True
if root.left:
if root.left.val <= start or root.left.val >= root.val:
return False
if root.right:
if root.right.val >= end or root.right.val <= root.val:
return False
tmpEnd = end
tmpStart = start
if root.val < end:
tmpEnd = root.val
if root.val > start:
tmpStart = root.val
return self.func(root.left, start, tmpEnd) and self.func(root.right, tmpStart, end)
def isValidBST(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
return self.func(root, -9999999999999, 999999999999999)