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.
Example
No.1
Input: root = {5,1,5,5,5,#,5}
Output: 4
Explanation:
No.2
Input: root = {1,3,2,4,5,#,6}
Output: 3
Explanation:
Code
1
2
3
4
5
6
|
public class {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
private int count = 0;
public int countUnivalSubtrees(TreeNode root) {
countHelper(root, -1);
return count;
}
private boolean countHelper(TreeNode root, int parent) {
if (root == null)
return true;
boolean left = countHelper(root.left, root.val);
boolean right = countHelper(root.right, root.val);
if (!left || !right) {
return false;
}
count++;
return root.val == parent;
}
|
近期评论