[leetcode]662. Maximum Width of Binary Tree(Python)

题目描述

Category：Medium Tree

Given a binary tree, write a function to get the maximum width of the given tree. The width of a tree is the maximum width among all levels. The binary tree has the same structure as a full binary tree, but some nodes are null.
The width of one level is defined as the length between the end-nodes (the leftmost and right most non-null nodes in the level, where the null nodes between the end-nodes are also counted into the length calculation.

题目理解

给定一棵二叉树，求二叉树的最大宽度。二叉树某层的宽度是指其最左节点与最右节点之间的跨度。

解题思路

层序遍历

层次遍历 + 完全二叉树的节点位置性质。这个性质指的是，每层都有 2 ^ (n-1)个节点。某节点的左孩子的标号是2n, 右节点的标号是2n + 1。因为这个题，中间缺少了节点的话，仍然要“认为”节点存在，所以需要使用这种标号的方法强制计算，而不是直接遍历。
思路借鉴：https://blog.csdn.net/fuxuemingzhu/article/details/79645897

class Solution:
    # Runtime: 32ms 86.49%  MemoryUsage: 13.1MB 100.00%
    def widthOfBinaryTree(self, root: TreeNode) -> int:
        queue = collections.deque()
        queue.append((root, 1))
        res = 0
        while queue:
            width = queue[-1][1] - queue[0][1] + 1
            res = max(width, res)
            for _ in range(len(queue)):
                n, c = queue.popleft()
                if n.left:
                    queue.append((n.left), c * 2)
                if n.right:
                    queue.append((n.right), c * 2 + 1)
        return res

哦我的天哪 我想了半天的递归、层序遍历也没想出来这种解法 只想着从已有的节点去推下一层的节点位置排列 忘记了用这种性质 遗憾

Time

2020.3.26 刷题的进度真的缓慢 这个作者是真的好强哦