题解 | #二叉树的最大宽度#

二叉树的最大宽度

http://www.nowcoder.com/practice/0975d62a307549cea32f353f354a7377

根据二插树的节点间的位置关系, left_child = root * 2, right_child = root * 2 + 1 利用层序遍历,进行判断处理

class Solution:
    def widthOfBinaryTree(self , root: TreeNode) -> int:
        """
            {1,2,3,4,#,4,5,6,#,1}
            {1,#,1,#,1 #,1,#,1,#,1,#,4,2}
        """
        # write code here
        if not root:
            return 0
        q = [(root, 0, 0)]
        dept = l_pos = 0
        res = 0
        for node, dep, pos in q:
            if node:
                q.append([node.left, dep + 1, pos * 2])
                q.append([node.right, dep + 1, pos * 2 + 1])
                if dept != dep:
                    dept = dep
                    l_pos = pos
                res = max(res, pos - l_pos + 1)
        return res

利用二插树的层序遍历,注意每一层的左侧和右侧不能是空值,在树节点及层数较少的情况下

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @return int整型
#
class Solution:
    def widthOfBinaryTree(self , root: TreeNode) -> int:
        """
            {1,2,3,4,#,4,5,6,#,1}
            {1,#,1,#,1,| #,1,|#,1,|#,1,|#,4,|2}
        """
        # write code here
        if not root:
            return 0
        q = [root]
        res = 0
        while q:
            res = max(res, len(q))
            ne = []
            for node in q:
                if node:
                    ne.append(node.left)
                    ne.append(node.right)
                else:
                    ne.append(None)
                    ne.append(None)
            while ne and ne[-1] == None:
                ne.pop()
            while ne and ne[0] == None:
                ne.pop(0)
            q = ne
        return res
                
题解 文章被收录于专栏

算法题解

全部评论

相关推荐

宇算唯航:目测实缴资本不超100W的小公司
点赞 评论 收藏
分享
半解316:内容充实,细节需要修改一下。 1,整体压缩为一页。所有内容顶格。 2,项目描述删除,直接写个人工作量 修改完之后还需要建议,可以私聊
点赞 评论 收藏
分享
人力小鱼姐:实习经历没有什么含金量,咖啡店员迎宾这种就别写了,其他两段包装一下 想找人力相关的话,总结一下个人优势,结合校园经历里有相关性的部分,加一段自我评价
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务