# 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 diameterOfBinaryTree(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root:
return 0
def height(root, ans):
if not root:
return 0
l = height(root.left, ans)
r = height(root.right, ans)
ans[0] = max(ans[0], l+r+1)
return max(l, r)+1

ans = [0]
height(root, ans)
return ans[0]-1


# 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 convertBST(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
if not root:
return None

def inorder(root, lst):
if not root:
return
inorder(root.left, lst)
lst.append(root)
inorder(root.right, lst)

nodes = []
inorder(root, nodes)
for i in xrange(len(nodes)-2, -1, -1):
nodes[i].val += nodes[i+1].val
return root


class Solution(object):
def updateMatrix(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[List[int]]
"""
n, m = len(matrix), len(matrix[0])
ans = [[0] * m for _ in xrange(n)]
cur = []
visited = set()
k = 0
for i in xrange(n):
for j in xrange(m):
if matrix[i][j] == 0:
cur.append((i, j))
while cur:
next = []
for i, j in cur:
ans[i][j] = k
for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
x, y = i+di, j+dj
if 0 <= x < n and 0 <= y < m and (x, y) not in visited:
next.append((x, y))
k += 1
cur = next

return ans


class Solution(object):
def findContestMatch(self, n):
"""
:type n: int
:rtype: str
"""
cur = [i for i in xrange(1, n+1)]
while len(cur) != 1:
next = []
for i in xrange(len(cur)/2):
next.append('({},{})'.format(cur[i], cur[len(cur)-i-1]))
cur = next
return cur[0]