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,
Given binary tree,
5 / \ 1 5 / \ \ 5 5 5
return
4
.
Solution 1: recursive DFS
public class Solution {
public int countUnivalSubtrees(TreeNode root) {
int[] count=new int[1];
dfs(root,count);
return count[0];
}
private boolean dfs(TreeNode x, int[] count) {
if (x==null) return true;
boolean left=dfs(x.left, count);
boolean right=dfs(x.right, count);
if (!left || !right) return false;
if (x.left!=null && x.val!=x.left.val) return false;
if (x.right!=null && x.val!=x.right.val) return false;
count[0]++;
return true;
}
}
没有评论:
发表评论