[LeetCode] 250. Count Univalue Subtrees 计算惟一值子树的个数

2021年09月15日 阅读数：1

Given a binary tree, count the number of uni-value subtrees.html

A Uni-value subtree means all nodes of the subtree have the same value.java

For example:
Given binary tree,node

```              5
/ \
1   5
/ \   \
5   5   5```

return `4`.python

Java:code

```/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
int count = 0;

public int countUnivalSubtrees(TreeNode root) {
if (root == null) return 0;
isUnival(root);
return count;
}

private boolean isUnival(TreeNode root) {
if (root == null) return true;
if (isUnival(root.left) & isUnival(root.right)) {
if (root.left != null && root.left.val != root.val) return false;
if (root.right != null && root.right.val != root.val) return false;
count++;
return true;
}
return false;
}
}　　```

Java:htm

```public class Solution {
public int countUnivalSubtrees(TreeNode root) {
int[] count = new int[] {0};
isUnivalSubtrees(root,count);
return count[0];
}

private boolean isUnivalSubtrees(TreeNode root, int[] count) {
if(root == null) return true;

boolean left = isUnivalSubtrees(root.left, count);
boolean right = isUnivalSubtrees(root.right, count);
if(left && right) {
if(root.left != null && root.left.val != root.val) {
return false;
}
if(root.right != null && root.right.val != root.val) {
return false;
}
count[0]++;
return true;
}
return false;
}
}　　```

Python:blog

```# Time:  O(n)
# Space: O(h)
class Solution(object):
# @param {TreeNode} root
# @return {integer}
def countUnivalSubtrees(self, root):
[is_uni, count] = self.isUnivalSubtrees(root, 0);
return count;

def isUnivalSubtrees(self, root, count):
if not root:
return [True, count]

[left, count] = self.isUnivalSubtrees(root.left, count)
[right, count] = self.isUnivalSubtrees(root.right, count)
if self.isSame(root, root.left, left) and \
self.isSame(root, root.right, right):
count += 1
return [True, count]

return [False, count]

def isSame(self, root, child, is_uni):
return not child or (is_uni and root.val == child.val)
```

C++:递归

```// Time:  O(n)
// Space: O(h)

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int countUnivalSubtrees(TreeNode* root) {
int count = 0;
isUnivalSubtrees(root, &count);
return count;
}

bool isUnivalSubtrees(TreeNode* root, int *count) {
if (root == nullptr) {
return true;
}
bool left = isUnivalSubtrees(root->left, count);
bool right = isUnivalSubtrees(root->right, count);
if (isSame(root, root->left, left) &&
isSame(root, root->right, right)) {
++(*count);
return true;
}
return false;
}

bool isSame(TreeNode* root, TreeNode* child, bool is_uni) {
return child == nullptr || (is_uni && root->val == child->val);
}
};
```

[LeetCode] 687. Longest Univalue Path 最长惟一值路径