Description
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.
Example
1 2 3 4 5 6 7 8 9
| Input: root = [5,1,5,5,5,null,5]
5 / \ 1 5 / \ \ 5 5 5
Output: 4
|
Solution
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
|
class Solution { int res = 0; public int countUnivalSubtrees(TreeNode root) { if (root == null) return 0; helper(root); return res; } private boolean helper(TreeNode root){ if (root == null) return true; if (root.left == null && root.right == null){ res++; return true; } boolean left = helper(root.left); boolean right = helper(root.right); if (!left || !right) return false; if (root.left == null){ if (root.val == root.right.val){ res++; return true; } } else if (root.right == null){ if (root.val == root.left.val){ res++; return true; } } else{ if (root.val == root.left.val && root.val == root.right.val){ res++; return true; } } return false; } }
|