# 250. Count Univalue Subtrees
## Level - ???
## Question
Given a binary tree, count the number of uni-value subtrees.

A Uni-value subtree means all nodes of the subtree have the same value.

Example :

Input: root = [5,1,5,5,5,null,5]

5
/ \
1 5
/ \ \
5 5 5

Output: 4

### Thought 1 - Recursive
It needs to subscribe leetcode to unlock. So I tried to do it by myself in detail.
We can assert it's a "unit value subtree" if all values in subtree are the same. So we write a isUni function to check whether it is. Be aware that each subtree needs to be checked.

# 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()

### Thought 2 - Recursive but more efficent
Get rid of those not necessary and redundant calculation. From leaf node to top, calculating uni value sub tree. Be aware that we need every isUni function, we cannot abandon it. So I wrote down it in two lines to get result rather than one condition.

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

### Thought 3 - Iterative
* Please remember how to write a Depth Search First in Postorder.
* Being in the res list means the subtree is unit value subtree.
* Add condition to find out suitable nodes.

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)