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.
This is a very good example to show different solutions to the tree problem.
Solution one, divide and conquer
Compute the result in the left subtree and right subtree. add them together, if the root.val is same to the all left value and all right value, add another one.
The problem is even if the root.val == root.left.val && root.val == root.right.val, we dont know whether all the node in the subtree have the same value, so we need to create a Result type to return mutiple types of result, the boolean specifies if all the nodes in the subtree are same, and the num states the number of univalue Subtree.
Code:
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { class Result{ boolean allSame; int num; public Result(boolean allSame, int num){ this.allSame = allSame; this.num = num; } } public int countUnivalSubtrees(TreeNode root) { return helper(root).num; } public Result helper(TreeNode root){ if(root == null) return new Result(true,0); Result left = helper(root.left); Result right = helper(root.right); int num = left.num + right.num; if(left.allSame && right.allSame && (root.left == null ? true : root.left.val == root.val) && (root.right == null ? true : root.right.val == root.val)){ return new Result(true, num + 1); } return new Result(false,num); } } Second Solution: Traverse and add.
We need to traverse to each node and count bottom up, we maintain a global varible to count.
public class Solution { int count; public int countUnivalSubtrees(TreeNode root) { helper(root); return count; } boolean helper(TreeNode root){ if(root == null) return true; if(root.left == null && root.right == null){ count += 1; return true; } boolean left = helper(root.left); boolean right = helper(root.right); if(left && right && (root.left == null ? true : root.left.val == root.val) && (root.right == null ? true : root.right.val == root.val)){ count += 1; return true; } return false; } }
