# 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 getMinimumDifference(self, root):
"""
:type root: TreeNode
:rtype: int
"""
ans = []
def inorder(root):
if not root:
return
inorder(root.left)
ans.append(root.val)
inorder(root.right)
inorder(root)
return min(ans[i+1]-ans[i] for i in xrange(len(ans)-1))


(s[j] - s[i]) % k == 0 and j - i >= 2

class Solution(object):

def checkSubarraySum(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: bool
"""
if k == 0:
for i in xrange(len(nums)-1):
if nums[i] == nums[i+1] == 0:
return True
else:
s = [0]
for n in nums:
s.append((s[-1]+n)%k)
d = {}
for i, n in enumerate(s):
j = d.get(n, i)
if j != i:
if i - j  >= 2:
return True
else:
d[n] = i
return False


class Solution(object):
def findLongestWord(self, s, d):
"""
:type s: str
:type d: List[str]
:rtype: str
"""
def check(w):
i = j = 0
while j < len(s):
while j < len(s) and w[i] != s[j]:
j += 1
if j < len(s):
i += 1
if i == len(w):
return True
j += 1
return False

t = filter(check, d)
ans = ''
for w in t:
if len(w) > len(ans) or (len(w) == len(ans) and w < ans):
ans = w
return ans


class Solution(object):

def updateBoard(self, board, click):
"""
:type board: List[List[str]]
:type click: List[int]
:rtype: List[List[str]]
"""
ans = []
for b in board:
ans.append(b[:])
n = len(ans)
if n == 0:
return ans
m = len(ans[0])
a, b = click
if ans[a][b] == 'M':
ans[a][b] = 'X'
return ans

d = [(-1, -1), (-1, 0), (-1, 1),
(0, -1), (0, 1),
(1, -1), (1, 0), (1, 1)]

queue = [(a, b)]
visited = set(queue)
i = 0
while i < len(queue):
a, b = queue[i]
c = 0
tmp = []
for da, db in d:
x, y = a+da, b+db
if x < 0 or y < 0 or x >= n or y >= m:
continue
if ans[x][y] == 'M' or ans[x][y] == 'X':
c += 1
if ans[x][y] == 'E' and (x, y) not in visited:
tmp.append((x, y))
ans[a][b] = str(c) if c != 0 else 'B'
if c == 0:
for x, y in tmp: