[daily coding problem] Counting Unival Subtrees

victor·2021년 2월 13일
0

목록 보기
26/63

code

public class UnivalTree {
public Node root;

public class Node {
public String value;
public Node left;
public Node right;
}

public boolean isUnival(Node root, value) {
if(root.value == null) return true;
if (root.value = value)
return isUnival(root.left, value) &&
isUnival(root.right, value);
return false;
}

public int countUnivalTree(Node root) {
if (root == null)
return 0;
int left = countUnivalTree(root.left);
int right = countUnivalTree(root.right);
if (isUnival(root)) return 1 + left + right;
else return left + right;
}

public static void main(String ...args) {
UnivalTree u = new UnivalTree();
u.root = new Node();
u.root.value = 'a';
u.root.right = new Node();
u.root.left = new Node();

int count = u.countUnivalTree(u.root);
System.out.println(count);
}

}

Time: O(n^2), cuz every time check if root is a unival tree, need to evalueate subtrees
Space: O(1)

• Better solution
what if count unival tree from each leaf?
const isUnival = root => {
if (root == undefined) return [0, true];
const [left, isLeftUnival] = isUnival(root.left);
const [right, isRightUnival] = isUnival(root.right);
let totalCount = left + right;

if (isLeftUnival && isRightUnival) {
if (root.left != undefined && root.value != root.left.value)
return [totalCount, false];
if (root.right != undefined && root.value != root.right.value)
return [totalCount, false];

totalCount += 1;
return [totalCount, true];
}

return [totalCount, false];
}


Time: O(n)
Space: O(1)

Example2) explanation
Unival tree count = 5

no/ = undefined

level1 a [1+4, false]
level2 c b [[0+0+1, true], [1+2+1, true]]
level3 no/ no/ b b [-, -, [0+0+1, true],[0+1+1, true]]
level4 no/ no/ no/ no/ no/ no/ no/ b [-, -, -, -, -, -, -, [0+0+1, True]]

캬-!