0250._Count_Univalue_Subtrees.md

250. Count Univalue Subtrees

难度: Medium

刷题内容

原题连接

• https://leetcode.com/problems/count-univalue-subtrees/

内容描述

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

解题方案

思路 1 - 时间复杂度: O(N)- 空间复杂度: O(1)******

递归，beats 100%

class Solution:
    def countUnivalSubtrees(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.res = 0
        def helper(node):
            if not node:
                return True
            if not node.left and not node.right:
                self.res += 1
                return True
            l = helper(node.left)
            r = helper(node.right)
            if l and r:
                if node.left and node.left.val != node.val:
                    return False
                if node.right and node.right.val != node.val:
                    return False
                self.res += 1
                return True
            else:
                return False
        helper(root)
        return self.res