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.
For example:
Given binary tree,
5
/ \
1 5
/ \ \
5 5 5
return 4.
Solution：递归 post-order 分治 upwards上传
思路：
Divide: left sub and right sub
Conquer: ifSame(boolean left, boolean right), int count, and then uploads
Time Complexity:T(N) = 2T(N / 2) + O(1) => O(N)
Space Complexity: O(N)
Solution Code：
public class Solution {
public int countUnivalSubtrees(TreeNode root) {
int[] count = new int[1];
helper(root, count);
return count[0];
}
private boolean helper(TreeNode node, int[] count) {
if (node == null) return true;
// divide
boolean left = helper(node.left, count);
boolean right = helper(node.right, count);
// conquer (ifSame(boolean left, boolean right), int count),
// and uploads ifSame & count
if (left && right) {
if (node.left != null && node.val != node.left.val) {
return false;
}
if (node.right != null && node.val != node.right.val) {
return false;
}
count[0]++;
return true;
}
return false;
}
}
