662. 二叉树最大宽度
给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（full binary tree）结构相同，但一些节点为空。
每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的null节点也计入长度）之间的长度。
示例 1:
输入:
1
/ \
3 2
/ \ \
5 3 9
输出: 4
解释: 最大值出现在树的第 3 层，宽度为 4 (5,3,null,9)。
示例 2:
输入:
1
/
3
/ \
5 3
输出: 2
解释: 最大值出现在树的第 3 层，宽度为 2 (5,3)。
示例 3:
输入:
1
/ \
3 2
/
5
输出: 2
解释: 最大值出现在树的第 2 层，宽度为 2 (3,2)。
示例 4:
输入:
1
/ \
3 2
/ \
5 9
/ \
6 7
输出: 8
解释: 最大值出现在树的第 4 层，宽度为 8 (6,null,null,null,null,null,null,7)。
注意: 答案在32位有符号整数的表示范围内。
原站题解
python3 解法, 执行用时: 48 ms, 内存消耗: 19.5 MB, 提交时间: 2022-08-29 10:55:14
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
'''
遍历时如果是先访问左子节点，再访问右子节点，
每一层最先访问到的节点会是最左边的节点，即每一层编号的最小值，需要记录下来进行后续的比较。
一次深度优先搜索中，需要当前节点到当前行最左边节点的宽度，
以及对子节点进行深度优先搜索，求出最大宽度，并返回最大宽度。
'''
class Solution:
def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
levelMin = {}
def dfs(node: Optional[TreeNode], depth: int, index: int) -> int:
if node is None:
return 0
if depth not in levelMin:
levelMin[depth] = index # 每一层最先访问到的节点会是最左边的节点，即每一层编号的最小值
return max(index - levelMin[depth] + 1,
dfs(node.left, depth + 1, index * 2),
dfs(node.right, depth + 1, index * 2 + 1))
return dfs(root, 1, 1)
golang 解法, 执行用时: 4 ms, 内存消耗: 5 MB, 提交时间: 2022-08-29 10:54:19
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
/**
* 遍历时如果是先访问左子节点，再访问右子节点，
* 每一层最先访问到的节点会是最左边的节点，即每一层编号的最小值，需要记录下来进行后续的比较。
* 一次深度优先搜索中，需要当前节点到当前行最左边节点的宽度，
* 以及对子节点进行深度优先搜索，求出最大宽度，并返回最大宽度。
*/
func widthOfBinaryTree(root *TreeNode) int {
levelMin := map[int]int{}
var dfs func(*TreeNode, int, int) int
dfs = func(node *TreeNode, depth, index int) int {
if node == nil {
return 0
}
if _, ok := levelMin[depth]; !ok {
levelMin[depth] = index // 每一层最先访问到的节点会是最左边的节点，即每一层编号的最小值
}
return max(index-levelMin[depth]+1, max(dfs(node.Left, depth+1, index*2), dfs(node.Right, depth+1, index*2+1)))
}
return dfs(root, 1, 1)
}
func max(a, b int) int {
if b > a {
return b
}
return a
}
golang 解法, 执行用时: 4 ms, 内存消耗: 4.4 MB, 提交时间: 2022-08-29 10:52:29
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
/*
* BFS, 此题求二叉树所有层的最大宽度，比较直观的方法是求出每一层的宽度，然后求出最大值。
* 求每一层的宽度时，因为两端点间的 null 节点也需要计入宽度，因此可以对节点进行编号。
* 一个编号为 index 的左子节点的编号记为 2×index，右子节点的编号记为 2×index+1，
* 计算每层宽度时，用每层节点的最大编号减去最小编号再加 1 即为宽度。
*/
type pair struct {
node *TreeNode
index int
}
func widthOfBinaryTree(root *TreeNode) int {
ans := 1
q := []pair{{root, 1}}
for q != nil {
ans = max(ans, q[len(q)-1].index-q[0].index+1)
tmp := q
q = nil
for _, p := range tmp {
if p.node.Left != nil {
q = append(q, pair{p.node.Left, p.index * 2})
}
if p.node.Right != nil {
q = append(q, pair{p.node.Right, p.index*2 + 1})
}
}
}
return ans
}
func max(a, b int) int {
if b > a {
return b
}
return a
}
python3 解法, 执行用时: 60 ms, 内存消耗: 16 MB, 提交时间: 2022-08-29 10:50:51
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
'''
BFS, 此题求二叉树所有层的最大宽度，比较直观的方法是求出每一层的宽度，然后求出最大值。
求每一层的宽度时，因为两端点间的 null 节点也需要计入宽度，因此可以对节点进行编号。
一个编号为 index 的左子节点的编号记为 2×index，右子节点的编号记为 2×index+1，
计算每层宽度时，用每层节点的最大编号减去最小编号再加 1 即为宽度。
'''
class Solution:
def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
res = 1
arr = [[root, 1]]
while arr:
tmp = []
for node, index in arr:
if node.left:
tmp.append([node.left, index * 2])
if node.right:
tmp.append([node.right, index * 2 + 1])
res = max(res, arr[-1][1] - arr[0][1] + 1)
arr = tmp
return res