LeetCode: Count Univalue Subtrees | CrazyEgg
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.
return
https://github.com/algorhythms/LeetCode/blob/master/250%20Count%20Univalue%20Subtrees.py
http://buttercola.blogspot.com/2015/09/leetcode-count-univalue-subtrees.html
X. Not efficient
https://discuss.leetcode.com/topic/55470/is-there-a-dp-solution-for-this-problem
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.
Best -
http://www.cnblogs.com/yrbbest/p/5011791.html
int count = 0;
https://discuss.leetcode.com/topic/20721/my-concise-java-solution
http://www.cnblogs.com/yrbbest/p/5011791.html
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; }http://happycoding2010.blogspot.com/2015/11/leetcode-250-count-univalue-subtrees.html
https://discuss.leetcode.com/topic/20721/my-concise-java-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;
} int countUnivalSubtrees(TreeNode* root) { int cnt = 0; helper(root, cnt); return cnt; } bool helper(TreeNode* root, int &cnt){ if(!root) return true; bool left = helper(root->left, cnt); bool right = helper(root->right, cnt); if(!left || !right) return false; if(root->left && root->left->val!=root->val) return false; if(root->right && root->right->val!=root->val) return false; cnt++; return true; }public int countUnivalSubtrees(TreeNode root) { if (root == null) { return 0; } if (root.left == null && root.right == null) { return 1; } int[] result = new int[]{0}; helper(root, result); return result[0]; } private boolean helper(TreeNode root, int[] result) { if (root.right == null && root.left == null) { result[0]++; return true; } else if (root.right != null && root.left == null) {
//don't check precondition before recursive-the base condition check does it. if (helper(root.right, result) && root.val == root.right.val) { result[0]++; return true; } else { return false; } } else if (root.right == null) { if (helper(root.left, result) && root.val == root.left.val) { result[0]++; return true; } else { return false; } } else { boolean l = helper(root.right, result); boolean r = helper(root.left, result); if (l && r && root.val == root.left.val && root.val == root.right.val) { result[0]++; return true; } else { return false; } } }http://ying.ninja/?p=886
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; // return true - make code cleaner } 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;}http://buttercola.blogspot.com/2015/09/leetcode-count-univalue-subtrees.html
X. Not efficient
https://discuss.leetcode.com/topic/55470/is-there-a-dp-solution-for-this-problem
int ret = 0;
public int countUnivalSubtrees(TreeNode root) {
helper(root);
return ret;
}
private void helper(TreeNode root){
if(root==null) return;
if(isUni(root)) ret++;
helper(root.left);
helper(root.right);
}
private boolean isUni(TreeNode root){
if(root==null || (root.left==null && root.right==null)) return true;
if(root.left!=null && root.val!=root.left.val) return false;
if(root.right!=null && root.val!=root.right.val) return false;
return (isUni(root.left) && isUni(root.right));
}