leetcode刷题笔记（1）二叉树+DFS搜索

leetcode98给定一个二叉树，判断其是否是一个有效的二叉搜索树。

class Solution:   
 def isValidBST(self, root: TreeNode) -> bool:      
     inorders = self.inorder(root)     
     return inorders ==sorted(set(inorders))
 def inorder(self,root):     
    if not root:         
      return []       
    return self.inorder(root.left)+[root.val]+self.inorder(root.right)  

letcode100 给定两个二叉树，编写一个函数来检验它们是否相同。

class Solution:   
     def isSameTree(self, p, q):     
         deq = [(p,q)]    
         while deq:       
              p,q = deq.pop(0) 
              if not p and not q:  
                   continue   
              if not p or not q:    
                   return False        
              if p.val != q.val:       
                   return False               
              deq.append((p.left,q.left))            
              deq.append((p.right,q.right))                      
              return True

leetcode104 二叉树的最大深度。

class Solution:    
     def maxDepth(self, root: TreeNode) -> int:     
        if not root :            
           return 0       
        else:       
              left = self.maxDepth(root.left)      
              right = self.maxDepth(root.right)                           
        return max(left, right) + 1

105. 从前序与中序遍历序列构造二叉树

class Solution: 
   def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:                   
            if not preorder:    
               return None     
            x = preorder.pop(0)     
            node = TreeNode(x)     
            i = inorder.index(x)    
            node.left = self.buildTree(preorder[:i], inorder[:i])    
            node.right = self.buildTree(preorder[i:], inorder[i+1:])                     
            return node 

106. 从中序与后序遍历序列构造二叉树

class Solution:    
      def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:             
          if not postorder:          
                  return None     
         x = postorder.pop()     
         node = TreeNode(x)     
         i = inorder.index(x)      
         node.left = self.buildTree(inorder[:i],postorder[:i])  
         node.right = self.buildTree(inorder[i+1:],postorder[i:])    
         return node

107. 将有序数组转换为二叉搜索树

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        if not nums:
           return None
        m = len(nums) // 2
        node = TreeNode(nums[m])
        node.left = self.sortedArrayToBST(nums[:m])
        node.right = self.sortedArrayToBST(nums[m+1:])
        return node 

108. 平衡二叉树

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        if  not root:
            return True
        if  abs(self.height(root.left)-self.height(root.right))>1:
            return False
        return self.isBalanced(root.left) and self.isBalanced(root.right)
    def height(self,root):
        if not root:
           return 0
        return max(self.height(root.left),self.height(root.right))+1    

109. 二叉树的最小深度

class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if not root:
           return 0
        queue = [(1,root)]
        while queue:
            dd,roots = queue.pop(0)
            children = [roots.left, roots.right]
            if not any(children):
               return dd 
            for sp in children:
                if sp:
                   queue.append((dd+1,sp)) 

110. 路径总和

class Solution:
    def hasPathSum(self, root: TreeNode, sum: int) -> bool:
        if not root:
            return False
        sum -= root.val
        if not root.left and not root.right:
            return sum==0
        return self.hasPathSum(root.left, sum) or self.hasPathSum(root.right, sum)

113. 路径总和 II

class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
        res = []
        result = []
        self.dfs1(root,sum,res,result)
        return result
    def dfs(self,root, sum, res, result):
        if not root:
           return 
        sum -= root.val
        if not root.left and not root.right and sum == 0:
           res += [root.val]
           result.append(res)
        self.dfs(root.left,sum,res + [root.val],result)   
        self.dfs(root.right,sum,res + [root.val],result)  

114. 二叉树展开为链表

class Solution:
    def flatten(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        if not root or (not root.left and not root.right) :
           return root
        self.flatten(root.left)
        self.flatten(root.right)
        temp = root.right
        root.right = root.left
        root.left = None
        while root.right:
              root = root.right
        root.right = temp   

115. 填充每个节点的下一个右侧节点指针 （bfs搜索）

class Solution: 
   def connect(self, root: 'Node') -> 'Node':   
        if not root:         
          return       
        stack = [root]     
        while stack:          
            temp = []           
            for sp in stack:       
                if  sp.left:        
                    temp.append(sp.left)       
                if  sp.right:                  
                    temp.append(sp.right)      
            for i in range(len(temp)-1):           
                   temp[i].next = temp[i+1]       
            stack = temp     
        return root                  

116. 求根到叶子节点数字之和

class Solution:
    def sumNumbers(self, root: TreeNode) -> int:
        if not root:
           return 0
        res = []
        result = []
        self.dfs(root,res,result)
        return sum(map(lambda x: int(''.join([str(t) for t in x ])) ,result))
    def dfs(self,root,res,result):
        if not root:
           return  
        if not root.left and not root.right:
           res += [root.val]
           result.append(res) 
        self.dfs(root.left,res+[root.val],  result)
        self.dfs(root.right,res+[root.val], result)            
        return result

130. 被围绕的区域

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        if not board or not board[0]:
            return
        row = len(board)
        col = len(board[0])
        for i in range(row):
            for j in [0,col-1]:
                if board[i][j] == 'O':
                   self.dfs(i,j,board) 
        for i in [0,row-1]:
            for j in range(1,col-1):            
                if board[i][j] == 'O': 
                    self.dfs(i,j,board) 
        for i in range(row):
            for j in range(col):
                    if board[i][j] == '*':
                       board[i][j] = 'O'
                    else:
                        board[i][j] = 'X'                   
    def dfs(self,i,j,board):                
        m = len(board)
        n = len(board[0])
        board[i][j] = '*'
        vec = [(0,1),(0,-1),(1,0),(-1,0)]
        for dx, dy in vec:
            nx , ny = i+dx ,j + dy
            if  0  <= nx < m and 0 <= ny < n and board[nx][ny] == 'O':
                self.dfs(nx, ny, board)

200. 岛屿数量

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid or not grid[0]:
            return 0
        m, n = len(grid), len(grid[0])
        count = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    count += 1
                    self.dfs(i, j, grid)
        return count

    def dfs(self, i, j, grid):
        vec = [(1, 0), (0, 1), (-1, 0), (0, -1)]
        grid[i][j] = '*'
        m, n = len(grid), len(grid[0])
        for nx, ny in vec:
            dx = i + nx
            dy = j + ny
            if 0 <= dx < m and 0 <= dy < n and grid[dx][dy] == '1':
                self.dfs(dx, dy, grid)
if  __name__ =='__main__':
    ss = Solution()
    dd = [["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]]
    ss.numIslands(dd)

257. 二叉树的所有路径

class Solution:
    def binaryTreePaths(self, root: TreeNode) -> List[str]:
        if not root:
           return []
        res = ''
        result = []
        self.dfs(root,res,result)
        return result
    def dfs(self,root,res,result):
        if not root:
           return
        if not root.left and not root.right:
           res = res + str(root.val)
           result.append(res)
           return result
        self.dfs(root.left,res+str(root.val)+ '->', result) 
        self.dfs(root.right,res+str(root.val)+ '->', result)

332. 重新安排行程

class Solution:
    def findItinerary(self, tickets) :
        dic,ss = {},[]
        for [sd,sf] in tickets:
            if sd not in dic:
                dic[sd] = [sf]
            else:
                dic[sd].append(sf)
                dic[sd].sort()
        print(dic)
        def dfs(f):  # 深搜函数
            while f in dic and dic[f]:
                dfs(dic[f].pop(0))  # 路径检索
            ss.insert(0, f)  # 放在最前
        dfs('JFK')
        return ss
if  __name__ == '__main__':
    s1 = Solution()
    sdd = [["JFK", "KUL"], ["JFK", "NRT"], ["NRT", "JFK"]]
    sd = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
    s1.findItinerary(sdd)

本文地址：https://blog.csdn.net/weixin_43214046/article/details/107141493