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.
For example:
Given binary tree,
5
/
1 5
/
5 5 5
return 4.
Python Solution 1:
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def countUnivalSubtrees(self, root):
"""
:type root: TreeNode
:rtype: int
"""
def postorder(root):
if not root:
return 0, True, None
l_res, l_valid, l_val = postorder(root.left)
r_res, r_valid, r_val = postorder(root.right)
if l_valid and r_valid and (l_val is None or l_val == root.val) and (r_val is None or r_val == root.val):
return l_res + r_res + 1, True, root.val
return l_res + r_res, False, None
res, valid, val = postorder(root)
return res
Python Solution 2:
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def countUnivalSubtrees(self, root):
"""
:type root: TreeNode
:rtype: int
"""
res = [0]
def postorder(root):
if not root:
return True, None
l_valid, l_val = postorder(root.left)
r_valid, r_val = postorder(root.right)
if l_valid and r_valid and (l_val is None or l_val == root.val) and (r_val is None or r_val == root.val):
res[0] += 1
return True, root.val
return False, None
postorder(root)
return res[0]
Summary:
- From bottom to top
LeetCode: 250. Count Univalue Subtrees
近期评论