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:
public int countUnivalSubtrees(TreeNode root) { int[] count = new int[1]; isUnivalSubtrees(root, count); return count[0]; } public boolean isUnivalSubtrees(TreeNode root, int[] count) { if (root == null) { return false; } boolean left = isUnivalSubtrees(root.left, count); boolean right = isUnivalSubtrees(root.right, count); if (!left && !right) { if (root.left == null && root.right == null) { count[0]++; return true; } } else if (left && right) { if (root.left.val == root.val && root.right.val == root.val) { count[0]++; return true; } } else if (left && !right) { if (root.right == null && root.left.val == root.val) { count[0]++; return true; } } else if (!left && right) { if (root.left == null && root.right.val == root.val) { count[0]++; return true; } } return false; }