python BFS和DFS LeetCode NO.102

系统 390 0

python BFS和DFS LeetCode

BFS主要用队列来实现,DFS主要用栈来实现

            
              
                #BFS模版
              
              
                def
              
              
                BFS
              
              
                (
              
              graph
              
                ,
              
              start
              
                ,
              
              end
              
                )
              
              
                :
              
              
	visited
              
                ,
              
              quene 
              
                =
              
              
                set
              
              
                (
              
              
                )
              
              
                ,
              
              
                [
              
              start
              
                ]
              
              
	visited
              
                .
              
              add
              
                (
              
              start
              
                )
              
              
                while
              
               queue
              
                :
              
              
		node 
              
                =
              
              quenue
              
                .
              
              pop
              
                (
              
              
                )
              
              
		visited
              
                .
              
              add
              
                (
              
              node
              
                )
              
              
		process
              
                (
              
              node
              
                )
              
              
		nodes 
              
                =
              
               generate_related_nodes
              
                (
              
              node
              
                )
              
              
		queuq
              
                .
              
              push
              
                (
              
              nodes
              
                )
              
            
          
            
              
                #DFS不完全代码,用于面试模版,递归写法
              
              
visited 
              
                =
              
              
                set
              
              
                (
              
              
                )
              
              
                def
              
              
                dfs
              
              
                (
              
              node
              
                ,
              
               visited
              
                )
              
              
                :
              
              
	visited
              
                .
              
              add
              
                (
              
              node
              
                )
              
              
                #对数据进行操作,
              
              
                .
              
              
                .
              
              
                .
              
              
                for
              
               next_node 
              
                in
              
               node
              
                .
              
              children
              
                (
              
              
                )
              
              
                :
              
              
                if
              
              
                not
              
               next_node 
              
                in
              
               visited
              
                :
              
              
					dfs
              
                (
              
              next_node
              
                ,
              
              visited
              
                )
              
              
                #非递归写法,类似于栈的结构
              
              
                def
              
               DFS(self
              
                .
              
               tree
              
                )
              
              
                :
              
              
                if
              
               tree
              
                .
              
              root 
              
                is
              
              
                None
              
              
                :
              
              
                return
              
              
                [
              
              
                ]
              
              
	visited
              
                ,
              
               stack 
              
                =
              
              
                {
              
              
                }
              
              
                ,
              
              
                [
              
              tree
              
                .
              
              root
              
                ]
              
              
                while
              
               stack
              
                :
              
              
		node
              
                =
              
               stack
              
                .
              
              pop
              
                (
              
              
                )
              
              
		visited
              
                .
              
              add
              
                (
              
              node
              
                )
              
              
                #处理数据部分
              
              
		process
              
                (
              
              node
              
                )
              
              
                #查找子节点,或者是相互连接的节点(对于图而言)
              
              
		nodes 
              
                =
              
               generate_related_nodes
              
                (
              
              node
              
                )
              
              
		stack
              
                .
              
              push
              
                (
              
              nodes
              
                )
              
            
          

python BFS和DFS LeetCode NO.102_第1张图片
如前文所述一样,BFS肯定是比较简单能想到的,用队列存储每一层的节点,然后一个一个的出队列,如果这个节点有孩子,那么就加入到队列中。当然也可以用DFS,DFS可以让面试官眼前一脸。

            
              
                class
              
              
                Solution
              
              
                (
              
              
                object
              
              
                )
              
              
                :
              
              
                def
              
              
                levelOrder
              
              
                (
              
              self
              
                ,
              
               root
              
                )
              
              
                :
              
              
                """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
              
              
                if
              
              
                not
              
               root 
              
                :
              
              
                return
              
               root
        
              
                if
              
              
                not
              
               root
              
                .
              
              left 
              
                and
              
              
                not
              
               root
              
                .
              
              right
              
                :
              
              
                return
              
              
                [
              
              
                [
              
              root
              
                .
              
              val
              
                ]
              
              
                ]
              
              
        cur 
              
                =
              
              
                [
              
              root
              
                ]
              
              
        res 
              
                =
              
              
                [
              
              
                ]
              
              
                while
              
               cur
              
                :
              
              
            nextStack
              
                ,
              
              tmp 
              
                =
              
              
                [
              
              
                ]
              
              
                ,
              
              
                [
              
              
                ]
              
              
                for
              
               node 
              
                in
              
               cur
              
                :
              
              
                tmp
              
                .
              
              append
              
                (
              
              node
              
                .
              
              val
              
                )
              
              
                if
              
               node
              
                .
              
              left
              
                :
              
              
                    nextStack
              
                .
              
              append
              
                (
              
              node
              
                .
              
              left
              
                )
              
              
                if
              
               node
              
                .
              
              right
              
                :
              
              
                    nextStack
              
                .
              
              append
              
                (
              
              node
              
                .
              
              right
              
                )
              
              
            cur 
              
                =
              
               nextStack
            res
              
                .
              
              append
              
                (
              
              tmp
              
                )
              
              
                return
              
               res

            
          
            
              
                # 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
              
              
                levelOrder
              
              
                (
              
              self
              
                ,
              
               root
              
                )
              
              
                :
              
              
                """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
              
              
                if
              
              
                not
              
               root
              
                :
              
              
                return
              
              
                [
              
              
                ]
              
              
        
        result 
              
                =
              
              
                [
              
              
                ]
              
              
        queue 
              
                =
              
               collections
              
                .
              
              deque
              
                (
              
              
                )
              
              
        queue
              
                .
              
              append
              
                (
              
              root
              
                )
              
              
                # visited = set(root)
              
              
                while
              
               queue
              
                :
              
              
            level_size 
              
                =
              
              
                len
              
              
                (
              
              queue
              
                )
              
              
            current_level 
              
                =
              
              
                [
              
              
                ]
              
              
                for
              
               _ 
              
                in
              
              
                range
              
              
                (
              
              level_size
              
                )
              
              
                :
              
              
                node 
              
                =
              
               queue
              
                .
              
              popleft
              
                (
              
              
                )
              
              
                current_level
              
                .
              
              append
              
                (
              
              node
              
                .
              
              val
              
                )
              
              
                if
              
               node
              
                .
              
              left
              
                :
              
               queue
              
                .
              
              append
              
                (
              
              node
              
                .
              
              left
              
                )
              
              
                if
              
               node
              
                .
              
              right
              
                :
              
              queue
              
                .
              
              append
              
                (
              
              node
              
                .
              
              right
              
                )
              
              
            
            result
              
                .
              
              append
              
                (
              
              current_level
              
                )
              
              
                return
              
               result

            
          
            
              
                # 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
              
              
                levelOrder
              
              
                (
              
              self
              
                ,
              
               root
              
                )
              
              
                :
              
              
                """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
              
              
                if
              
              
                not
              
               root
              
                :
              
              
                return
              
              
                [
              
              
                ]
              
              
        self
              
                .
              
              result 
              
                =
              
              
                [
              
              
                ]
              
              
        self
              
                .
              
              _dfs
              
                (
              
              root
              
                ,
              
              
                0
              
              
                )
              
              
                return
              
               self
              
                .
              
              result
    
    
              
                def
              
              
                _dfs
              
              
                (
              
              self
              
                ,
              
               node
              
                ,
              
               level
              
                )
              
              
                :
              
              
                if
              
              
                not
              
               node
              
                :
              
              
                return
              
              
                if
              
              
                len
              
              
                (
              
              self
              
                .
              
              result
              
                )
              
              
                <
              
              level 
              
                +
              
              
                1
              
              
                :
              
              
            self
              
                .
              
              result
              
                .
              
              append
              
                (
              
              
                [
              
              
                ]
              
              
                )
              
              
            
        self
              
                .
              
              result
              
                [
              
              level
              
                ]
              
              
                .
              
              append
              
                (
              
              node
              
                .
              
              val
              
                )
              
              
        
        self
              
                .
              
              _dfs
              
                (
              
              node
              
                .
              
              left
              
                ,
              
               level
              
                +
              
              
                1
              
              
                )
              
              
        self
              
                .
              
              _dfs
              
                (
              
              node
              
                .
              
              right
              
                ,
              
              level
              
                +
              
              
                1
              
              
                )
              
            
          

更多文章、技术交流、商务合作、联系博主

微信扫码或搜索:z360901061

微信扫一扫加我为好友

QQ号联系: 360901061

您的支持是博主写作最大的动力,如果您喜欢我的文章,感觉我的文章对您有帮助,请用微信扫描下面二维码支持博主2元、5元、10元、20元等您想捐的金额吧,狠狠点击下面给点支持吧,站长非常感激您!手机微信长按不能支付解决办法:请将微信支付二维码保存到相册,切换到微信,然后点击微信右上角扫一扫功能,选择支付二维码完成支付。

【本文对您有帮助就好】

您的支持是博主写作最大的动力,如果您喜欢我的文章,感觉我的文章对您有帮助,请用微信扫描上面二维码支持博主2元、5元、10元、自定义金额等您想捐的金额吧,站长会非常 感谢您的哦!!!

发表我的评论
最新评论 总共0条评论