https://binarysearch.com/problems/Univalue-Tree-Count
A univalue tree is a tree where all nodes under it have the same value.
Given a binary tree root, return the number of univalue subtrees.
Constraints:
1 ≤ n ≤ 100,000 where n is the number of nodes in root
intuition
Tree Traversals: Postorder by DFS
- you need check left subtree
- if left == null, return true;
- if left != null, deep check left, and compare left.value with now_node.val
- you need check right subtree
- if right == null, return true;
- if right != null, deep tracking right, and compare right.value with now_node.val
- compare left with right if they are equal with true, ans += 1
Implementation
Basic Postorder by using DFS
void postorder(Node node) {
if (node == null)
return;
// traverse the left child
postorder(node.left);
// traverse the right child
postorder(node.right);
// traverse the root node
System.out.print(node.item + "->");
}
Time Complexity
O(n): you need check all nodes in the tree
Space Complexity
O(n): you need do recursion into tree level
class Solution {
int count = 0;
public int solve(Tree root) {
checkUnivalue(root);
return count;
}
private boolean checkUnivalue(Tree node) {
boolean left = node.left == null || (checkUnivalue(node.left) && node.left.val == node.val);
boolean right = node.right == null || (checkUnivalue(node.right) && node.right.val == node.val);
boolean isUnivalue = left && right;
// A simpler way by using & calculate both side simultaneously
// boolean isUnivalue =
// (node.left == null || checkUnivalue(node.left) && node.left.val == node.val)
// & (node.right == null || checkUnivalue(node.right) && node.right.val == node.val);
count += isUnivalue ? 1 : 0;
return isUnivalue;
}
}
Top comments (0)