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. (意思是忆植，該subtree下所有節(jié)點(diǎn)都相同，所以第二層的1辛润，和根節(jié)點(diǎn)的5不是 Uni-value subtree)
Example :
Input: root = [5,1,5,5,5,null,5]
5
/ \
1 5
/ \ \
5 5 5
Output: 4
Solution: Bottom-Up recursion
- 從當(dāng)前節(jié)點(diǎn)口叙，拿到其
left,right子節(jié)點(diǎn)是否是Uni-value subtree - 再根據(jù)左右子樹的信息暂吉，判斷當(dāng)前節(jié)點(diǎn)是否是
Uni-value subtree- 如果任一一個不是, 那么當(dāng)前節(jié)點(diǎn)就不是
Uni-value subtree。 - 如果左右子樹都是
Uni-value subtree，再判斷root.val == root.left.val ? && root.val == root.right.val
- 如果任一一個不是, 那么當(dāng)前節(jié)點(diǎn)就不是
如果當(dāng)前節(jié)點(diǎn)是Uni-value subtree檐迟，那么global_count ++
Note: 有一種情況需處理专普，即 current node 只有左子樹或只有右子樹悯衬，且current node val == 其某一子樹的val, 這種情況當(dāng)前節(jié)點(diǎn)也是Uni-value subtree
if ((isLeftUnival && isRightUnival)
&& (root.left == null || root.left.val == root.val)
&& (root.right == null || root.right.val == root.val))
- 返回當(dāng)前節(jié)點(diǎn)是否是
uni-value subtree
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int countUnivalSubtrees(TreeNode root) {
if (root == null) {
return 0;
}
int[] count = { 0 };
countUnivalSubtrees (root, count);
return count[0];
}
private boolean countUnivalSubtrees (TreeNode root, int[] count) {
if (root == null) {
return true;
}
boolean isLeftUnival = countUnivalSubtrees(root.left, count);
boolean isRightUnival = countUnivalSubtrees(root.right, count);
if ((isLeftUnival && isRightUnival)
&& (root.left == null || root.left.val == root.val)
&& (root.right == null || root.right.val == root.val)) {
count [0]++;
return true;
}
return false;
}
}
