image.png

思路：DFS + 标号

  • BFS非常容易，层次遍历不难
  • DFS需要两个标记，一个记录当前深度depth，一个记录当前的节点的标号index

  • 节点标号：一层一层，从左往右写，节点不存在也占用标号，也就是

    1. `node.left.val = 2 * val + 1`和`node.right.val = 2 * val + 2`（第一个根节点从0开始）

  • 相同层的将标号放到一起，然后算最后一个节点的标号减去当前层第一个节点的标号。

  • 关键还是在于节点标号的思想。

    代码：

# 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:
        # 宽搜比较容易
        # 深搜也可以做
        recPos = collections.defaultdict(list)
        self.maxWidth = 0

        def dfs(root: Optional[TreeNode], index: int, depth: int) -> None:
            if not root:
                return
            recPos[depth].append(index)
            dfs(root.left, 2 * index + 1, depth + 1)
            dfs(root.right, 2 * index + 2, depth + 1)
            self.maxWidth = max(self.maxWidth, recPos[depth][-1] - recPos[depth][0] + 1)

        dfs(root, 0, 0)
        return self.maxWidth