欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

leetcode刷题笔记(1)二叉树+DFS搜索

程序员文章站 2022-04-19 13:20:25
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:...

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
  1. 从前序与中序遍历序列构造二叉树
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 
  1. 从中序与后序遍历序列构造二叉树
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
  1. 将有序数组转换为二叉搜索树
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 
  1. 平衡二叉树
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    
  1. 二叉树的最小深度
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)) 
  1. 路径总和
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)
  1. 路径总和 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)  
  1. 二叉树展开为链表
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   
  1. 填充每个节点的下一个右侧节点指针 (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                  
  1. 求根到叶子节点数字之和
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
  1. 被围绕的区域
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)
  1. 岛屿数量
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)
  1. 二叉树的所有路径
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)
  1. 重新安排行程
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