今晚吃的是韩式烧烤：羊肉和豆腐。

这次比赛有四题，题目都比较基础，可惜打错了一个变量名字WA了一次。

第一题Diameter of Binary Tree

题目大意：一棵树的直径定义为树中最长路径的长度。给定一棵二叉树，求树的直径。

递归想法：对于每个树节点，计算经过该树节点最长路径的长度。只要修改求每个节点高度的程序就行。先算当前左子树的高度l和右子树的高度r，那么以该经过该节点最长路径的长度就是l+r+1，然后返回该节点的高度max(l, r)+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 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

第二题Convert BST to Greater Tree

题目大意：给定一棵二叉搜索树（BST），将其转成Greater Tree：将原来BST的每个节点的值加上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 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

第三题01 Matrix

题目大意：给定一个01矩阵，求每个元素与其最近的0的路径长度。

我使用了宽度优先想法：首先从所有的0出发，一层一层地往外扩张。

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))
                    visited.add((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))
                        visited.add((x, y))
            k += 1
            cur = next

        return ans

第四题Output Contest Matches

题目大意：其实相当于找规律。。。我就不描述了，直接给样例。 样例1: Input: 2 Output: (1,2) 样例2: Input: 4 Output: ((1,4),(2,3)) 样例3: Input: 8 Output: (((1,8),(4,5)),((2,7),(3,6)))

找到规律就行：初始化一个列表cur，保存一个从1到n的字符串，然后每次进行一下操作直至列表长度为1。新的cur列表的第i个位置是旧cur列表中的第i个与第len(cur)-i-1组合而来。

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]
leetcode contest