ahasusie
commented
5 years ago
class Solution(object):
def rangeSumBST(self, root, L, R):
def dfs(node):
if node:
if L <= node.val <= R:
self.ans += node.val
if L < node.val:
dfs(node.left)
if node.val < R:
dfs(node.right)
self.ans = 0
dfs(root)
return self.ans
class Solution(object):
def rangeSumBST(self, root, L, R):
ans = 0
stack = [root]
while stack:
node = stack.pop()
if node:
if L <= node.val <= R:
ans += node.val
if L < node.val:
stack.append(node.left)
if node.val < R:
stack.append(node.right)
return ans
[4,5,6,7,8,0,1,2]
def search(arr, num):
l, r = 0, len(arr)-1
while l<=r:
mid = l+(r-l)//2
if arr[mid] == num:
return mid
if arr[l] <= arr[mid]: # left part is sorted
if arr[l] <= num <= arr[mid]:
r = mid-1 #search sorted left part
else:
l = mid+1 #search unsorted right part
else: # right part is sorted
if arr[mid] <= num <= arr[r]:
l = mid+1 #search sorted right part
else:
r = mid-1 #search unsorted left part
return -1
# looking for the largest number that is smaller than target, return left
def insert(arr, target):
l, r = 0, len(arr)-1
while l<=r:
mid = l+(r-l)//2
if arr[mid] == target:
return mid
if arr[mid] < target:
l = mid+1
else:
r = mid-1
return l
l, r = 0, len(arr)-1
while l+1<r:
mid = l+(r-l)//2
if arr[mid] == target:
return mid
if arr[mid] < target:
l = mid
else:
r = mid
if arr[l] == target:
return l
if arr[r] == target:
return r
if arr[l] < target < arr[r]:
return l+1
if arr[l] > target:
return l
if arr[r] < target:
return r+1
###############################################################################
# !!!!!IMPORTANT
###############################################################################
def biSearch(arr, val):
l, r = 0, len(arr)-1
while l<=r:
mid = l+(r-l)//2
if arr[mid] < val:
l = mid+1
else:
r = mid-1
print arr[l], arr[r]
def bsLeft(arr, val):
l, r = 0, len(arr)-1
while l<=r:
mid = l+(r-l)//2
if arr[mid] >= val:
r = mid-1
else:
l = mid+1
print arr[l], arr[r]
def bsRight(arr, val):
l, r = 0, len(arr)-1
while l<=r:
mid = l+(r-l)//2
if arr[mid] <= val:
l = mid+1
else:
r = mid-1
print arr[l], arr[r]
if __name__ == "__main__":
arr = [1,3,5,5,7,9]
biSearch(arr, 4) #search for value's left and right, value not in arr, don't warried about arr[mid] == val, val not in arr anyway.
bsLeft(arr, 5) #search for value's left, value in arr, no matter if has duplicates
bsRight(arr, 5) #search for value's right, value in arr, no matter if has duplicates
#################################################################################################
l<=r end:l-1=r l+1<r end l+1=r l<r end:l=r