类型：树
-
- 二叉树最大宽度 💛 ⭐
https://leetcode-cn.com/problems/maximum-width-of-binary-tree/
❓ 计算一棵树的最大宽度。
输入: 1 / \ 3 2 / \ \ 5 3 9 输出: 4 解释: 最大值出现在树的第 3 层，宽度为 4 (5,3,null,9)。💡 此题的主要方法是给每一个结点记录一个 position 值，如果我们走向左子树，那么 pos → pos * 2，如果我们走向右子树，那么 pos → pos * 2 + 1。通过同一层最两端的结点的 pos，就可以计算该层的宽度：R - L + 1。
💡 BFS
def widthOfBinaryTree(self, root): queue = [(root, 0, 0)] cur_depth = left = ans = 0 for node, depth, pos in queue: if node: queue.append((node.left, depth+1, pos*2)) queue.append((node.right, depth+1, pos*2 + 1)) if cur_depth != depth: # 说明我们到了新的一层 cur_depth = depth left = pos ans = max(pos - left + 1, ans) return ans时间复杂度：O(n)，空间复杂度：O(n)
💡 DFS
对于每一个深度，第一个到达的位置会被记录在 left[depth] 中。
然后对于每一个节点，它对应这一层的可能宽度是 pos - left[depth] + 1 。我们将每一层这些可能的宽度取一个最大值就是答案。
class Solution(object): def widthOfBinaryTree(self, root): self.ans = 0 left = {} def dfs(node, depth = 0, pos = 0): if node: left.setdefault(depth, pos) self.ans = max(self.ans, pos - left[depth] + 1) dfs(node.left, depth + 1, pos * 2) dfs(node.right, depth + 1, pos * 2 + 1) dfs(root) return self.ans时间复杂度：O(n)，空间复杂度：O(n)