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

根据二插树的节点间的位置关系, 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