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
|
// 1361. Validate Binary Tree Nodes
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
/*
* you have n binary trees nodes numbered from 0 to n - 1 where node i has two
* children left_child and right_child. return true if any only if all the given
* nodes from exactly one valid binary tree. if node i has no left children,
* then left_child[i] will equal -1. note that the nodes have no values and that
* we only use the node numbers in this problem.
*/
bool validateBinaryTreeNodes(int n, int *left_child, int left_child_size,
int *right_child, int right_child_size) {
bool *flag = calloc(n, sizeof(bool));
for (int i = 0; i < n; i++) {
if (left_child[i] == -1)
continue;
flag[left_child[i]] = true;
}
for (int i = 0; i < n; i++) {
if (right_child[i] == -1)
continue;
flag[right_child[i]] = true;
}
int root = -1;
for (int i = 0; i < n; i++) {
if (!flag[i]) {
if (root == -1)
root = i;
else
return false;
}
}
if (root == -1)
return false;
bool *visited = calloc(n, sizeof(bool));
int *stack = malloc(2 * n * sizeof(int));
int count = 0;
stack[count] = root;
count++;
int p = 0, node = 0;
while (p < count) {
node++;
int left = left_child[stack[p]];
int right = right_child[stack[p]];
visited[stack[p]] = true;
p++;
if (left != -1) {
if (visited[left] == true)
return false;
stack[count] = left;
count++;
}
if (right != -1) {
if (visited[right] == true)
return false;
stack[count] = right;
count++;
}
}
free(flag), free(visited);
if (node == n)
return true;
return false;
}
int main() {
int lc1[] = {1, -1, 3, -1}, rc1[] = {2, -1, -1, -1};
int lc2[] = {1, -1, 3, -1}, rc2[] = {2, 3, -1, -1};
int lc3[] = {1, 0}, rc3[] = {-1, -1};
printf("%d\n", validateBinaryTreeNodes(4, lc1, 4, rc1, 4)); // expect: 1
printf("%d\n", validateBinaryTreeNodes(4, lc2, 4, rc2, 4)); // expect: 0
printf("%d\n", validateBinaryTreeNodes(2, lc3, 2, rc3, 2)); // expect: 0
}
|