LeetCode 250. Подсчет Univalue
Учитывая бинарное дерево, подсчитайте количество поддеревьев с уникальным значением.
Поддерево с однозначным значением означает, что все узлы поддерева имеют одинаковое значение.
Пример :
Input: root = [5,1,5,5,5,null,5] 5 / \ 1 5 / \ \ 5 5 5 Output: 4
Для разблокировки необходимо подписаться на leetcode. Поэтому я попытался сделать это самостоятельно в деталях.
Мысль 1 — рекурсия в каждом поддереве
Мы можем утверждать, что это «поддерево единичных значений», если все значения в поддереве одинаковы. Поэтому мы пишем функцию isUni, чтобы проверить, так ли это. Имейте в виду, что необходимо проверять каждое поддерево.
# 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 __init__(self): self.res = 0 def buildTree(self): self.root = TreeNode(5) self.root.left = TreeNode(1) self.root.right = TreeNode(5) self.root.left.left = TreeNode(5) self.root.left.right = TreeNode(5) self.root.right.right = None self.root.right.left = TreeNode(5) def countUniValueSubtrees(self, root: TreeNode) -> int: # Define is unit value subtree def isUni(root, val): if not root: return True return (root.val==val) and isUni(root.left, root.val) and (isUni(root.left, root.val)) if not root: return self.res if isUni(root, root.val): self.res += 1 self.countUniValueSubtrees(root.left) self.countUniValueSubtrees(root.right) return self.res def run(self): print(self.countUniValueSubtrees(self.root)) solution = Solution() solution.buildTree() solution.run()
Мысль 2 — Рекурсивно, но более эффективно
Избавьтесь от ненужных и избыточных вычислений. От конечного узла к вершине, вычисление поддерева с уникальными значениями. Имейте в виду, что нам нужна каждая функция isUni, мы не можем от нее отказаться. Поэтому я записал его в две строки, чтобы получить результат, а не одно условие.
def countUniValueSubtrees(self, root: TreeNode) -> int: # Define is unit value subtree def isUni(root, val): if not root: return True resLeft = isUni(root.left, root.val) resRight = isUni(root.right, root.val) if not (resLeft and resRight): return False self.res += 1 return root.val==val isUni(root, -1) return self.res
Идея 3 – Итеративность
- Пожалуйста, помните, как написать поиск глубины сначала в постпорядке (используйте стек, чтобы сохранить последовательность обхода. Голова должна различать, что узел должен идти вниз на следующий уровень или заканчиваться здесь).
- Нахождение в списке res означает, что поддерево является поддеревом единичных значений, поэтому мы можем сравнить значение левого узла «хороших» поддеревьев с собственным значением. Если оно такое же, значит, это тоже «хорошее» поддерево. Как и правое поддерево.
- Добавьте условия, чтобы найти подходящие узлы. Смотрите ниже код напрямую.
def countUniValueSubtrees(self, root: TreeNode) -> int: res = [] s = [root] # Stack head = root while s: node = s[-1] # If it's (leaf node) or (traversaled left node) or (traversaled right node) if (not node.left and not node.right) or (node.left == head) or (node.right == head): # If it's leaf node if not node.left and not node.right: res.append(node) # If left node is NULL and right node is "unit value subtree" abd node value is equals to right node value elif (not node.left) and (node.right in res) and (node.val == node.right.val): res.append(node) # The same concept is used on right node elif (not node.right) and (node.left in res) and (node.val == node.left.val): res.append(node) # Those nodes on the middle path need to compair its left and right node value to its value to decide whether it is unit value subtree. elif (node.left and node.right) and (node.left in res) and (node.right in res) and (node.val == node.right.val) and (node.val == node.right.val): res.append(node) head = s.pop() else: if node.left: s.append(node.left) if node.right: s.append(node.right) return len(res)