leetcode LCP 开幕式焰火

LCP 44. 开幕式焰火 - 力扣（LeetCode）

「力扣挑战赛」开幕式开始了，空中绽放了一颗二叉树形的巨型焰火。 给定一棵二叉树 root 代表焰火，节点值表示巨型焰火这一位置的颜色种类。请帮小扣计算巨型焰火有多少种不同的颜色。

示例 1：

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

输出：3

解释：焰火中有 3 个不同的颜色，值分别为 1、2、3

示例 2：

输入：root = [3,3,3]

输出：1

解释：焰火中仅出现 1 个颜色，值为 3

提示：

• 1 <= 节点个数 <= 1000
• 1 <= Node.val <= 1000

为了解决这个问题，我们需要遍历二叉树并收集所有节点的值，然后计算这些值中不同的数量。我们可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来遍历二叉树。这里，我将使用DFS来解决这个问题。

步骤

1. 定义一个集合来存储所有不同的节点值。
2. 使用DFS遍历二叉树，将每个节点的值添加到集合中。
3. 遍历结束后，集合的大小即为不同颜色的数量。

class Solution:def numColor(self, root: TreeNode) -> int:# 初始化一个空集合s，用于存储遍历过程中遇到的所有不同颜色s = set()# 定义一个深度优先搜索（DFS）的辅助函数def dfs(node: Optional[ListNode]) -> None:# 如果当前节点为空，直接返回，不进行任何操作if node is None:return# 将当前节点的颜色（值）添加到集合s中# 由于集合的特性，相同的值不会被重复添加s.add(node.val)# 递归地对当前节点的左子节点进行DFSdfs(node.left)# 递归地对当前节点的右子节点进行DFSdfs(node.right)# 从根节点root开始，调用DFS函数进行遍历dfs(root)# 遍历结束后，集合s中存储的就是所有不同的颜色# 返回集合s的大小，即不同颜色的数量return len(s)

解释

• 我们首先定义了一个集合 values 来存储不同的节点值。
• 然后定义了一个 dfs 函数来递归地遍历二叉树。在 dfs 函数中，我们首先检查当前节点是否为空，如果为空则返回。否则，我们将当前节点的值添加到集合中，并递归地遍历其左右子树。
• 最后，我们从根节点开始调用 dfs 函数，并返回集合 values 的大小，即不同颜色的数量。

这个方法的时间复杂度是 O(n)，其中 n 是二叉树的节点个数，因为我们需要遍历每个节点一次。空间复杂度是 O(n)，因为最坏情况下，集合 values 可能包含所有节点的值。