题目描述
-
题意是说如果一个结点的左子树和右子树的值都相等, 那么就计数+1. 因此我们只需要一个递归的判定一个结点出发,是否其所有结点都相等即可.叶子结点也算是一个结果.
-
关于python 全局变量 Self.ans , 可以独立于递归函数 DFS
也就是说, 不要写成 def DFS(self, x, y, ans):
写成 def DFS(self, x, y)
就可以了
样例
blablabla
算法1
blablabla
时间复杂度
参考文献
Python3 代码
# 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):
if not root:
return 0
self.ans = 0
self.dfs(root, root.val)
return self.ans
def dfs(self,root, pre):
if not root:
return True
flag1 = self.dfs(root.left,root.val)
flag2 = self.dfs(root.right,root.val)
if flag1 and flag2:
self.ans +=1
return (root.val == pre) and flag1 and flag2