题目描述

1. 题意是说如果一个结点的左子树和右子树的值都相等, 那么就计数+1. 因此我们只需要一个递归的判定一个结点出发,是否其所有结点都相等即可.叶子结点也算是一个结果.

2. 关于python 全局变量 Self.ans ， 可以独立于递归函数 DFS
   也就是说， 不要写成 def DFS(self, x, y, ans):
   写成 def DFS(self, x, y)
   就可以了

样例

blablabla

算法1

迭代 $O(n)$

blablabla

时间复杂度$O(n)$

讲真，上面的时间复杂度，我也不确定。

参考文献

python3 代码

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