LeetCode 腾讯50题Python实现之《二叉树的最大深度》

系统 131 0

题目

给定一个二叉树,找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例:
给定二叉树 [3,9,20,null,null,15,7],

            
              3

            
          

/
9 20
/
15 7
返回它的最大深度 3 。

思路

BFS广度优先搜索,使用双端队列deque(因为性能比另外两种Queue好得多),在大循环内对二叉树的每个层做一次遍历,range(len(queue))使只遍历当前的层,每次大循环ans加1。由于每个节点仅访问一次,所以时间复杂度O(n)

代码

            
              
                import
              
               collections

              
                class
              
              
                Solution
              
              
                :
              
              
                def
              
              
                maxDepth
              
              
                (
              
              self
              
                ,
              
               root
              
                :
              
               TreeNode
              
                )
              
              
                -
              
              
                >
              
              
                int
              
              
                :
              
              
                if
              
              
                not
              
               root
              
                :
              
              
                return
              
              
                0
              
              
        queue 
              
                =
              
               collections
              
                .
              
              deque
              
                (
              
              
                )
              
              
        queue
              
                .
              
              append
              
                (
              
              root
              
                )
              
              
        ans 
              
                =
              
              
                0
              
              
                while
              
               queue
              
                :
              
              
            ans 
              
                +=
              
              
                1
              
              
                for
              
               _ 
              
                in
              
              
                range
              
              
                (
              
              
                len
              
              
                (
              
              queue
              
                )
              
              
                )
              
              
                :
              
              
                node 
              
                =
              
               queue
              
                .
              
              popleft
              
                (
              
              
                )
              
              
                if
              
               node
              
                .
              
              left
              
                :
              
              
                    queue
              
                .
              
              append
              
                (
              
              node
              
                .
              
              left
              
                )
              
              
                if
              
               node
              
                .
              
              right
              
                :
              
              
                    queue
              
                .
              
              append
              
                (
              
              node
              
                .
              
              right
              
                )
              
              
                return
              
               ans


            
          

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

微信扫码或搜索:z360901061

微信扫一扫加我为好友

QQ号联系: 360901061

您的支持是博主写作最大的动力,如果您喜欢我的文章,感觉我的文章对您有帮助,请请扫描上面二维码支持博主1元、2元、5元等您想捐的金额吧,狠狠点击下面给点支持吧

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