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
.Recursion.
public class CountUnivalueSubtrees { int count = 0; public int countUnivalSubtrees(TreeNode root) { if (root == null) { return count; } validTree(root); return count; } private boolean validTree(TreeNode root) { if (root == null) { return true; } if (root.left == null || root.right == null) { count++; return true; } boolean left = validTree(root.left); boolean right = validTree(root.right); if (left && right && ( (root.left == null && root.val == root.right.val) || (root.right == null && root.val == root.left.val) || (root.val == root.left.val && root.val == root.right.val) )) { count++; return true; } return false; } }
No comments:
Post a Comment