0662. Maximum Width of Binary Tree

662. Maximum Width of Binary 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.

Example 1:

``````Input:

1
/   \
3     2
/ \     \
5   3     9

Output: 4
Explanation: The maximum width existing in the third level with the length 4 (5,3,null,9).
``````

Example 2:

``````Input:

1
/
3
/ \
5   3

Output: 2
Explanation: The maximum width existing in the third level with the length 2 (5,3).
``````

Example 3:

``````Input:

1
/ \
3   2
/
5

Output: 2
Explanation: The maximum width existing in the second level with the length 2 (3,2).
``````

Example 4:

``````Input:

1
/ \
3   2
/     \
5       9
/         \
6           7
Output: 8
Explanation:The maximum width existing in the fourth level with the length 8 (6,null,null,null,null,null,null,7).
``````

Note: Answer will in the range of 32-bit signed integer.

解题思路 #

• 给出一个二叉树，求这棵树最宽的部分。
• 这一题可以用 BFS 也可以用 DFS，但是用 BFS 比较方便。按照层序遍历，依次算出每层最左边不为 `null` 的节点和最右边不为 `null` 的节点。这两个节点之间都是算宽度的。最终输出最大的宽度即可。此题的关键在于如何有效的找到每一层的左右边界。
• 这一题可能有人会想着先补全满二叉树，然后每层分别找左右边界。这种方法提交以后会卡在 `104 / 108` 这组测试用例上，这组测试用例会使得最后某几层填充出现的满二叉树节点特别多，最终导致 `Memory Limit Exceeded` 了。
• 由于此题要找每层的左右边界，实际上每个节点的 `Val` 值是我们不关心的，那么可以把这个值用来标号，标记成该节点在每层中的序号。父亲节点在上一层中的序号是 x，那么它的左孩子在下一层满二叉树中的序号是 `2*x`，它的右孩子在下一层满二叉树中的序号是 `2*x + 1`。将所有节点都标上号，用 BFS 层序遍历每一层，每一层都找到左右边界，相减拿到宽度，动态维护最大宽度，就是本题的最终答案。

代码 #

``````
package leetcode

/**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
func widthOfBinaryTree(root *TreeNode) int {
if root == nil {
return 0
}
if root.Left == nil && root.Right == nil {
return 1
}

queue, res := []*TreeNode{}, 0
queue = append(queue, &TreeNode{0, root.Left, root.Right})

for len(queue) != 0 {
var left, right *int
// 这里需要注意，先保存 queue 的个数，相当于拿到此层的总个数
qLen := len(queue)
// 这里循环不要写 i < len(queue)，因为每次循环 queue 的长度都在变小
for i := 0; i < qLen; i++ {
node := queue[0]
queue = queue[1:]
if node.Left != nil {
// 根据满二叉树父子节点的关系，得到下一层节点在本层的编号
newVal := node.Val * 2
queue = append(queue, &TreeNode{newVal, node.Left.Left, node.Left.Right})
if left == nil || *left > newVal {
left = &newVal
}
if right == nil || *right < newVal {
right = &newVal
}
}
if node.Right != nil {
// 根据满二叉树父子节点的关系，得到下一层节点在本层的编号
newVal := node.Val*2 + 1
queue = append(queue, &TreeNode{newVal, node.Right.Left, node.Right.Right})
if left == nil || *left > newVal {
left = &newVal
}
if right == nil || *right < newVal {
right = &newVal
}
}
}
switch {
// 某层只有一个点，那么此层宽度为 1
case left != nil && right == nil, left == nil && right != nil:
res = max(res, 1)
// 某层只有两个点，那么此层宽度为两点之间的距离
case left != nil && right != nil:
res = max(res, *right-*left+1)
}
}
return res
}

``````

Apr 8, 2023