难度: Medium
Submission
运行时间: 26 ms
内存: 16.2 MB
class Solution:
def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:
if root is None:
return 0
count = 0
def isUnivalSubtree(node: Optional[TreeNode]) -> bool:
nonlocal count
if node.left is None and node.right is None:
count += 1
return True
isUnival = True
if node.left is not None:
isUnival = isUnivalSubtree(node.left) and isUnival and node.left.val == node.val
if node.right is not None:
isUnival = isUnivalSubtree(node.right) and isUnival and node.right.val == node.val
if isUnival:
count += 1
return True
else:
return False
isUnivalSubtree(root)
return count
# 作者：力扣官方题解
# 链接：https://leetcode.cn/problems/count-univalue-subtrees/solutions/2477598/tong-ji-tong-zhi-zi-shu-by-leetcode-solu-7orv/
# 来源：力扣（LeetCode）
# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
Explain
该题解采用递归的思路。对于每个节点，递归地判断其左右子树是否为同值子树。如果当前节点是叶子节点，则直接返回 True，并将计数器加 1。否则，分别递归判断左右子树。如果左右子树都是同值子树，且当前节点与左右子节点的值相同，则当前节点也是同值子树，将计数器加 1 并返回 True；否则返回 False。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:
if root is None:
return 0
count = 0
def isUnivalSubtree(node: Optional[TreeNode]) -> bool:
nonlocal count
# 如果当前节点是叶子节点，则直接返回 True，并将计数器加 1
if node.left is None and node.right is None:
count += 1
return True
isUnival = True
# 递归判断左子树是否为同值子树
if node.left is not None:
isUnival = isUnivalSubtree(node.left) and isUnival and node.left.val == node.val
# 递归判断右子树是否为同值子树
if node.right is not None:
isUnival = isUnivalSubtree(node.right) and isUnival and node.right.val == node.val
# 如果左右子树都是同值子树，且当前节点与左右子节点的值相同，则当前节点也是同值子树
if isUnival:
count += 1
return True
else:
return False
isUnivalSubtree(root)
return count
Explore
在`isUnivalSubtree`函数中，对于当前节点的左右子节点的空值情况进行了特别的处理。如果子节点为`None`（即不存在），则该子节点不会对判断当前节点是否为同值子树产生影响。这是因为在函数中仅当子节点存在时（即`node.left is not None`和`node.right is not None`），才会检查该子节点的值是否与当前节点的值相同，并将结果与`isUnival`进行逻辑与操作。如果子节点不存在，那么对应的条件分支不会执行，因而`isUnival`的值不会受到影响。
在代码中，一旦`isUnival`被设置为`False`，它不会在当前递归调用中被重新设为`True`。这是因为`isUnival`一旦确定当前节点不构成同值子树，就没有必要再改变其值，因为已经确定当前树枝不满足同值子树的条件。这种处理确保了一旦子树中的任何部分不符合同值子树的条件，整个子树都不会被错误地计数为同值子树，从而避免了错误的计数和不必要的递归，提高了效率和准确性。
统计同值子树的数量时，通过逐个节点递归地调用`isUnivalSubtree`函数，并在确认一个节点的子树满足同值子树条件时立即增加计数器来确保不会重复计数。每个节点只有在其作为根的子树被确定为同值子树时才增加计数，且每个节点只作为根被检查一次。这种方式保证了每个符合条件的同值子树只被计算一次，无论其大小或位置如何，从而避免了重复计数的可能性。