250. Count-Univalue-Subtrees.md

Description

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

---

python solution

先遍历二叉树，对于在遍历过程中的每个节点node_i，以它为根节点进行子树遍历，将子树中所有值保存到一个列表arr中，如果这个arr中所有元素都相等，那么cnt += 1

这其实是一个二重递归，在递归过程中对每一个节点再次进行递归

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def countUnivalSubtrees(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
		# 遍历root为为根节点的子树，将每个元素的值保存到arr中
        def traversal(root, arr):
            if not root: return
            arr.append(root.val)
            traversal(root.left, arr)
            traversal(root.right, arr)

        self.univalCnt = 0

        def judgeUnivalTrees(root):
            if not root: return
            # 遍历以root为根节点的子树，如果所有元素都相等 => univalCnt += 1
            arr = []
            traversal(root, arr)
            if len(set(arr)) == 1:
                self.univalCnt += 1

            judgeUnivalTrees(root.left)
            judgeUnivalTrees(root.right)

        judgeUnivalTrees(root)
        return self.univalCnt