Мало знаний, большой вызов! Эта статья участвует в "Необходимые знания для программистов«Творческая деятельность.
【Ежедневные пробные серии】
LeetCode200 простых вопросов
Описание темы
Началась церемония открытия «Licco Challenge», и в воздухе расцвел гигантский фейерверк в форме бинарного дерева. Учитывая, что корень двоичного дерева представляет фейерверк, значение узла представляет цвет гигантского фейерверка в этом месте. Пожалуйста, помогите Сяокоу подсчитать, сколько разных цветов у гигантского фейерверка.
Пример 1:
входить:
root = [1,3,2,1,null,2]
вывод:3
Объяснение: В фейерверке 3 разных цвета, значения 1, 2, 3
Пример 2:
входить:
root = [3,3,3]
вывод:1
Объяснение: В фейерверке появляется только 1 цвет со значением 3.
намекать
1 <= 节点个数 <= 10001 <= Node.val <= 1000
Идеи решения проблем
Смысл заголовка легко понять: пройдитесь по бинарному дереву, чтобы получить значение цвета каждого узла, и верните длину путем дедупликации. Затем реализация кода может сначала определить набор для сохранения уникального значения значения цвета, полученного путем обхода.Здесь двоичное дерево проходится с использованием метода обхода глубины.Условие рекурсивного завершенияnodeзаNone. То есть после перехода к листовому узлу запишите соответствующийnodeизvalзначение, чтобы начать откат. После завершения обхода бинарного дерева вернитесь напрямуюlen(res)это цветотип.
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def numColor(self, root):
"""
:type root: TreeNode
:rtype: int
"""
res = set()
def DFS(node):
if not node: return
DFS(node.left)
DFS(node.right)
res.add(node.val)
DFS(root)
return len(res)
Сегодняшняя регистрация завершена, и текущий прогресс — 3/200.