# 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 findTilt(self, root):
"""
:type root: TreeNode
:rtype: int
"""
ans = [0]

def dfs(root):
if not root:
return 0
left = dfs(root.left)
right = dfs(root.right)
ans[0] += abs(left-right)
return left+right+root.val

dfs(root)
return ans[0]


(a1, b1), ..., (an, bn)

class Solution(object):
def arrayPairSum(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
nums.sort()
return sum(nums[i] for i in xrange(0, len(nums), 2))


class Solution(object):
def longestLine(self, M):
"""
:type M: List[List[int]]
:rtype: int
"""
n = len(M)
if n == 0:
return 0
m = len(M[0])
if m == 0:
return 0

row = [[False] * m for _ in xrange(n)]
col = [[False] * m for _ in xrange(n)]
dia = [[False] * m for _ in xrange(n)]
ant = [[False] * m for _ in xrange(n)]
ans = 0
for i in xrange(n):
for j in xrange(m):
if M[i][j] == 0:
continue
if not row[i][j]:
k = j
while k < m and M[i][k] == 1:
row[i][k] = True
k += 1
ans = max(ans, k-j)
if not col[i][j]:
k = i
while k < n and M[k][j] == 1:
col[k][j] = True
k += 1
ans = max(ans, k-i)
if not dia[i][j]:
k, t = i, j
while k < n and t < m and M[k][t] == 1:
dia[k][t] = True
k += 1
t += 1
ans = max(ans, k-i)
if not ant[i][j]:
k, t = i, j
while k < n and t >= 0 and M[k][t] == 1:
ant[k][t] = True
k += 1
t -= 1
ans = max(ans, k-i)
return ans


class Solution(object):
def nearestPalindromic(self, n):
"""
:type n: str
:rtype: str
"""
def smaller(n):
m = list(n)
for i in xrange(len(m)/2):
m[len(n)-1-i] = m[i]
m = ''.join(m)
if m < n:
return m
n1 = str(int(n[:(len(n)+1)/2])-1)
n2 = '9' * (len(n) - (len(n)+1)/2)
if n1 != '0':
n = n1+n2
else:
n = n2
if n == '':
return '0'
if n == n[::-1]:
return n
return smaller(n1+n2)

def bigger(n):
m = list(n)
for i in xrange(len(m)/2):
m[len(n)-1-i] = m[i]
m = ''.join(m)
if m > n:
return m
n1 = str(int(n[:(len(n)+1)/2])+1)
n2 = '0' * (len(n) - (len(n)+1)/2)
n = n1+n2
if n == n[::-1]:
return n
return bigger(n1+n2)

s = smaller(n)
b = bigger(n)
if int(n)-int(s) <= int(b)-int(n):
return s
else:
return b