本文共 11026 字，大约阅读时间需要 36 分钟。

• ：求树的最大深度, Easy

class Solution(object):    def maxDepth(self, root):        """        :type root: TreeNode        :rtype: int        """        if not root: return 0        return max(self.maxDepth(root.left),self.maxDepth(root.right))+1

• ：求最大岛屿面积，Easy

  dfs+记忆化搜索

class Solution(object):    def maxAreaOfIsland(self, grid):        """        :type grid: List[List[int]]        :rtype: int        """        m = len(grid)        if m == 0: return 0        n = len(grid[0])        disvisited = [[True for j in range(n)] for i in range(m)]        def dfs(ii,jj):            ret = 0            dx = [0,0,-1,1]            dy = [1,-1,0,0]            for k in range(4):                x = ii + dx[k]                y = jj + dy[k]                if x>=0 and x
   
    =0 and y
   

• ：求指定id和其所有下属的总主要性，Easy

class Solution(object):    def getImportance(self, employees, id):        """        :type employees: Employee        :type id: int        :rtype: int        """        emp = dict()        visited = dict()        for employee in employees:            emp[employee.id] = employee        def dfs(idx):            if idx in visited:                return 0            visited[idx] = True            ret=emp[idx].importance            for sub in emp[idx].subordinates:                ret+=dfs(sub)            return ret        return dfs(id)

• ：从出发点(sr,sc)开始，与之相连的有相同像素的点都换成newColor, Easy

class Solution(object):    def floodFill(self, image, sr, sc, newColor):        """        :type image: List[List[int]]        :type sr: int        :type sc: int        :type newColor: int        :rtype: List[List[int]]        """        m = len(image)        if m == 0: return image        n = len(image[0])        disvisited = [[True for j in range(n)] for i in range(m)]        rawColor = image[sr][sc]        def dfs(xx,yy):            disvisited[xx][yy] = False            image[xx][yy] = newColor            dx = [0,0,-1,1]            dy = [1,-1,0,0]            for k in range(4):                x = xx+dx[k]                y = yy+dy[k]                if x>=0 and x
   
    =0 and y
   

• ：判断两个树是否相同，Easy

# Definition for a binary tree node.# class TreeNode(object):#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass Solution(object):    def isSameTree(self, p, q):        """        :type p: TreeNode        :type q: TreeNode        :rtype: bool        """        if p is None and q is None:            return True        elif p is None or q is None:            return False        else:            if p.val==q.val:                if self.isSameTree(q.left,p.left):                    return self.isSameTree(p.right,q.right)            return False

• ：把一个有序列表转化为二叉搜索树，Easy

  根据二叉搜索树的性质，左树上的值<根结点的值<右树上的值

  因此可以取 nums/2 位置上的值作为根结点的值，然后再左右递归调用即可

# Definition for a binary tree node.# class TreeNode(object):#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass Solution(object):    def sortedArrayToBST(self, nums):        """        :type nums: List[int]        :rtype: TreeNode        """        length = len(nums)        if length==0:            return None        if length == 1:            return TreeNode(nums[0])        root = TreeNode(nums[length/2])        root.left = self.sortedArrayToBST(nums[:(length/2)])        root.right =self.sortedArrayToBST(nums[(length/2+1):])        return root

• ：判断树是否是对称树，Easy

# Definition for a binary tree node.# class TreeNode(object):#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass Solution(object):    def isSymmetric(self, root):        """        :type root: TreeNode        :rtype: bool        """        if root==None:            return True        return self.symetric(root.left,root.right)    def symetric(self,root_a,root_b):        if root_a==None and root_b==None:            return True        if root_a==None or root_b==None:            return False        if root_a.val !=root_b.val:            return False        return self.symetric(root_a.left,root_b.right) and self.symetric(root_a.right,root_b.left)

• ：打印二叉树的所有路径，Easy

# Definition for a binary tree node.# class TreeNode(object):#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass Solution(object):    def binaryTreePaths(self, root):        """        :type root: TreeNode        :rtype: List[str]        """        ret = []        if root == None:            return ret        cur_val = root.val        if root.left:            ret += self.binaryTreePaths(root.left)        if root.right:            ret += self.binaryTreePaths(root.right)        if ret == []:            return [str(cur_val)]        else:            for i in range(len(ret)):                ret[i] = str(cur_val)+'->'+ret[i]            return ret

• ：判断二叉树是否是平衡二叉树，Easy

  左子树是否平衡+右子树是否平衡+左右子树的高度差<=1

# Definition for a binary tree node.# class TreeNode(object):#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass Solution(object):    def height(self,root):        if root == None:            return 0        if root.left == None and root.right == None:            return 1        return max(self.height(root.left),self.height(root.right))+1    def isBalanced(self, root):        """        :type root: TreeNode        :rtype: bool        """        if root ==None:            return True        return self.isBalanced(root.left) and self.isBalanced(root.right) and abs(self.height(root.left)-self.height(root.right))<=1

• ：求二叉树的最小深度，Easy

# Definition for a binary tree node.# class TreeNode(object):#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass Solution(object):    def minDepth(self, root):        """        :type root: TreeNode        :rtype: int        """        if root == None:            return 0        if root.left == None and root.right !=None:            return self.minDepth(root.right)+1        if root.right == None and root.left !=None:            return self.minDepth(root.left)+1        return min(self.minDepth(root.left),self.minDepth(root.right))+1

• ：求二叉树最后一行最左边的值，Medium

  题外话，这题BFS的速度比DFS快很多，我两个都贴出来了

# Definition for a binary tree node.# class TreeNode(object):#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass Solution(object):    def findBottomLeftValueDFS(self, root):        """        :type root: TreeNode        :rtype: int        """        if root == None: return 0        def dfs(root,step):            maxstep = step            val = root.val            if root.left:                leftstep,lval = dfs(root.left,step+1)                if leftstep>maxstep:                    maxstep = leftstep                    val = lval            if root.right:                rightstep,rval = dfs(root.right,step+1)                if rightstep>maxstep:                    maxstep = rightstep                    val = rval            return maxstep,val        maxstep,val = dfs(root,0)        return val    def findBottomLeftValueBFS(self, root):        """        :type root: TreeNode        :rtype: int        """        if root == None: return 0        queue = [root]        while(queue):            tmp = []            for q in queue:                if q.left:                    tmp.append(q.left)                if q.right:                    tmp.append(q.right)            if tmp == []:                return queue[0].val            queue = tmp[:]

• ：求每一层结点的最大值，Medium

  DFS: dict()+dfs

  BFS: 逐层判断

# Definition for a binary tree node.# class TreeNode(object):#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass Solution(object):    def largestValues(self, root):        """        :type root: TreeNode        :rtype: List[int]        """        steps = dict()        def dfs(root,step):            if root is None:                return             if step not in steps:                steps[step] = root.val            else:                steps[step] = max(steps[step],root.val)            if root.left:                dfs(root.left,step+1)            if root.right:                dfs(root.right,step+1)        dfs(root,0)        ans = sorted(steps.items(),key=lambda x:x[0])        ret = list(map(lambda x:x[1],ans))        return ret    def largestValuesBFS(self, root):        """        :type root: TreeNode        :rtype: List[int]        """        if root is None: return []        queue = [root]        ret = []        while(queue):            tmp = []            val = None            for q in queue:                if q.left:                    tmp.append(q.left)                if q.right:                    tmp.append(q.right)                if val is None: val = q.val                else:                    val = max(val,q.val)            queue = tmp[:]            ret.append(val)        return ret

• 扫雷游戏，如果东西南北加对角线没有雷的话，则标记为’B’，同时沿着8个方向递归；如果东西南北加对角线有雷的话，则标记为’E’；如果踩到雷的话，则标记为’X’, Medium

class Solution(object):    def updateBoard(self, board, click):        """        :type board: List[List[str]]        :type click: List[int]        :rtype: List[List[str]]        """        m = len(board)        if m == 0: return board        n = len(board[0])        if board[click[0]][click[1]] == 'M':            board[click[0]][click[1]] = 'X'            return board        disvisited = [[True for j in range(n)] for i in range(m)]        def dfs(i,j):            disvisited[i][j] = False            dx = [1,1,1,0,0,-1,-1,-1]            dy = [0,1,-1,1,-1,0,1,-1]            flag = 0            for k in range(8):                x = dx[k]+i                y = dy[k]+j                if x>=0 and x
   
    =0 and y
    
     =0 and x
     
      =0 and y
     
    
   

• 给定一个数组，玩家只能从两端取数，判断第一个玩家取数之和是否能够大于第二个玩家，Medium

dfs+记忆化搜索

class Solution(object):    def PredictTheWinner(self, nums):        """        :type nums: List[int]        :rtype: bool        """        cache = dict()        def dfs(tnums):            if len(tnums)<=1: return sum(tnums)            tnums = tuple(tnums)            if tnums in cache: return cache[tnums]            ans = max(tnums[0]-dfs(tnums[1:]),tnums[-1]-dfs(tnums[:-1]))            cache[tnums] = ans            return cache[tnums]         return dfs(nums)>=0

• 购买不同产品有不同的单价花费，同时也提供组合套餐，问购买指定组数目产品所需的最少费用

class Solution(object):    def shoppingOffers(self, price, special, needs):        """        :type price: List[int]        :type special: List[List[int]]        :type needs: List[int]        :rtype: int        """        dp = dict()        def dfs(tup):            if tup in dp:                return dp[tup]            dp[tup]=sum([t*p for t,p in zip(tup,price)])            for sp in special:                new_tup = tuple([t-st for t,st in zip(tup,sp)])                if min(new_tup)<0:                    continue                dp[tup] = min(dp[tup], dfs(new_tup) + sp[-1])            return dp[tup]        return dfs(tuple(needs))

to be continue

转载地址：http://fbqmi.baihongyu.com/