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)