二叉树的最大宽度

题目表述

给你一棵二叉树的根节点 root ，返回树的 最大宽度 。

树的 最大宽度 是所有层中最大的 宽度 。

每一层的 宽度 被定义为该层最左和最右的非空节点（即，两个端点）之间的长度。将这个二叉树视作与满二叉树结构相同，两端点间会出现一些延伸到这一层的 null 节点，这些 null 节点也计入长度。

题目数据保证答案将会在 32 位 带符号整数范围内。

示例 1

输入：root = [1,3,2,5,3,null,9]

输出：4

解释：最大宽度出现在树的第 3 层，宽度为 4 (5,3,null,9)。

示例 2

输入：root = [1,3,2,5,null,null,9,6,null,7]

输出：7

解释：最大宽度出现在树的第 4 层，宽度为 7 (6,null,null,null,null,null,7)。

示例 3

输入：root = [1,3,2,5]

输出：2

解释：最大宽度出现在树的第 2 层，宽度为 2 (3,2) 。

提示

树中节点的数目范围是 [1, 3000]

-100 <= Node.val <= 100

解法一：广度优先搜索

求每一层的宽度时，因为两端点间的 null 节点也需要计入宽度，因此可以对节点进行编号。一个编号为 index 的左子节点的编号记为 2×index，右子节点的编号记为 2×index+1，计算每层宽度时，用每层节点的最大编号减去最小编号再加 1 即为宽度。

遍历节点时，可以用广度优先搜索来遍历每一层的节点，并求出最大值。

时间复杂度和空间复杂度都为O(n)

代码实现

from typing import Optional

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    """BFS 搜索"""
    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        # 对节点进行编号
        nodes = [[root, 0]]
        max_width = 1
        while nodes:
            max_width = max([max_width, nodes[-1][1] - nodes[0][1]+1])
            new_nodes = []
            for node, i in nodes:
                if node.left:
                    new_nodes.append([node.left, 2*i])
                if node.right:
                    new_nodes.append([node.right, 2*i+1])
            nodes = new_nodes
        return max_width

package leetcode

// BFS 遍历
func widthOfBinaryTree(root *TreeNode) int {
	type TreeNodeIndex struct {
		Index int
		*TreeNode
	}
	nodes := []TreeNodeIndex{{0, root}}
	maxWidth := 1
	for len(nodes) > 0 {
		width := nodes[len(nodes)-1].Index - nodes[0].Index + 1
		if width > maxWidth {
			maxWidth = width
		}
		newNodes := []TreeNodeIndex{}
		for _, node := range nodes {
			if node.Left != nil {
				newNodes = append(newNodes, TreeNodeIndex{2 * node.Index, node.Left})
			}
			if node.Right != nil {
				newNodes = append(newNodes, TreeNodeIndex{2*node.Index + 1, node.Right})
			}
		}
		nodes = newNodes
	}
	return maxWidth
}

解法二：深度优先搜索

仍然按照上述方法编号，可以用深度优先搜索来遍历。遍历时如果是先访问左子节点，再访问右子节点，每一层最先访问到的节点会是最左边的节点，即每一层编号的最小值，需要记录下来进行后续的比较。一次深度优先搜索中，需要当前节点到当前行最左边节点的宽度，以及对子节点进行深度优先搜索，求出最大宽度，并返回最大宽度。

时间复杂度和空间复杂度都为O(n)

代码实现

from typing import Optional

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution2:
    """DFS 搜索"""
    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        level_min_index = {} # 每层最小节点的 index
        def dfs(node: TreeNode, depth: int, index: int)->int:
            if not node:
                return 0
            if depth not in level_min_index:
                level_min_index[depth] = index
            
            lwidth = dfs(node.left, depth+1,index*2)
            rwidth = dfs(node.right, depth+1,index*2+1)
            cur_width = index - level_min_index[depth]+1
            return max(lwidth, rwidth, cur_width)
        return dfs(root, 1, 1)

package leetcode

// DFS 遍历
func widthOfBinaryTree2(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 // 每一层最先访问到的节点会是最左边的节点，即每一层编号的最小值
		}
		childWidth := max(dfs(node.Left, depth+1, index*2), dfs(node.Right, depth+1, index*2+1))
		return max(index-levelMin[depth]+1, childWidth)
	}
	return dfs(root, 1, 1)
}

func max(a, b int) int {
	if b > a {
		return b
	}
	return a
}