javascript-things/DailyCodingProblem/Easy/P8.js at master · karan1205/javascript-things · GitHub

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
/**
 * This problem was asked by Google.
 * A unival tree (which stands for "universal value") is a tree where all nodes under it have the same value.
 * Given the root to a binary tree, count the number of unival subtrees.
 * For example, the following tree has 5 unival subtrees:
 *    0
 *   / \
 *  1   0
 *     / \
 *    1   0
 *   / \
 *  1   1
*/

function checkUnival(root, data) {
	if(!root) return true;
	if(data !== root.data) return false;
	return checkUnival(root.left, data) && checkUnival(root.right, data);
}

function countUnivalTrees(root) {
	let count = 0;

	function traverse(root) {
		if(!root.left && !root.right) {
			return ++count;
		}
		if(root.left) {
			traverse(root.left);
		}
		if(root.right) {
			traverse(root.right);
		}
		if(checkUnival(root, root.data)) {
			count++;
		}
		return count;
	}

	return root ? traverse(root) : count;
}

const tree = {
	data: 0,
	left: {
		data: 1,
		left: null,
		right: null,
	},
	right: {
		data: 0,
		left: {
			data: 1,
			left: {
				data: 1,
				left: null,
				right: null,
			},
			right: {
				data: 1,
				left: null,
				right: null,
			}
		},
		right: {
			data: 0,
			left: null,
			right: null,
		}
	}
}

const result = countUnivalTrees(tree);
console.log(result);