难度: Easy
运行时间: 30 ms
内存: 16.4 MB
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def numColor(self, root: TreeNode) -> int:
s = set()
def dfs(node):
if node is None:
return
dfs(node.left)
s.add(node.val)
dfs(node.right)
dfs(root)
return len(s)
这个题解使用了深度优先搜索（DFS）来遍历整棵二叉树，并利用一个集合（set）来存储遍历过程中遇到的所有不同的节点值。通过这种方式，集合中的元素个数最终就是不同颜色的总数。首先，定义一个辅助函数dfs来递归遍历树的每一个节点。如果当前节点为空，则递归结束。否则，先递归遍历左子树，然后将当前节点的值添加到集合中，最后递归遍历右子树。这样可以确保每个节点都被访问一次。最后，返回集合中元素的数量，即为不同颜色的总数。
时间复杂度: O(n)
空间复杂度: O(n)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def numColor(self, root: TreeNode) -> int:
s = set() # 初始化一个空集合来存储不同颜色
def dfs(node):
if node is None: # 如果节点为空，返回
return
dfs(node.left) # 递归访问左子树
s.add(node.val) # 将当前节点的值加入集合
dfs(node.right) # 递归访问右子树
dfs(root) # 从根节点开始DFS
return len(s) # 返回集合中元素的个数，即不同颜色的总数
在这个问题中，无论是使用深度优先搜索（DFS）还是广度优先搜索（BFS），都可以有效地遍历整棵树并处理每个节点。选择DFS主要是因为它的实现较为简单直接，特别是在递归形式的实现中，代码更加简洁。DFS可以直接利用递归的方式访问每一个节点，而BFS则需要额外的数据结构，如队列，来存储每一层的节点。因此，从实现的复杂性和直观性考虑，DFS是一个合适的选择。此外，对于问题的解决并无明显性能差异，使得DFS成为一个简洁有效的选择。
在这个算法中，集合（set）用于存储遍历过程中遇到的所有不同的节点值。由于集合的特性是不允许存储重复元素，每当尝试将一个已经存在于集合中的值再次添加到集合时，该操作会被忽略。这样，集合中的元素个数始终反映了遇到的不同节点值的数量，即不同的颜色数。因此，集合是通过其独特的数据结构特性来帮助确定和记录树中所有独特颜色的数量。最终，返回集合的大小即可得到不同颜色的总数。
是的，如果二叉树非常深，使用递归形式的深度优先搜索（DFS）确实存在栈溢出的风险，因为每一层递归调用都会占用一定的栈空间，如果递归层数过多，可能会导致栈空间耗尽。为了避免这种情况，可以使用迭代的方式来实现DFS，通常借助一个显式的栈数据结构来手动模拟递归过程。在迭代版本的DFS中，使用一个栈来存储接下来需要访问的节点，这样可以有效控制栈的使用，避免因递归过深而导致的栈溢出问题。