diff options
Diffstat (limited to 'even_odd_tree.c')
-rw-r--r-- | even_odd_tree.c | 76 |
1 files changed, 76 insertions, 0 deletions
diff --git a/even_odd_tree.c b/even_odd_tree.c new file mode 100644 index 0000000..0cae3e8 --- /dev/null +++ b/even_odd_tree.c @@ -0,0 +1,76 @@ +// 1609. Even Odd Tree +#include "leetcode.h" + +/* + * a binary tree is even-odd if it meets the following conditions. the root of + * the binary tree is at level index 0 it s children are at level index 1 and + * their children are at level index 2, etc. for every even indexed level, all + * nodes at the level have odd integer values in strictly ordere (from left to + * right). for every odd-indexed level, all nodes at the level have even integer + * values in strictly decreasing order (from left to right). given 'root' of a + * binary tree, return true if the binary tree is even-odd, otherwise return + * false. + */ + +struct TreeNode { + int val; + struct TreeNode *left, *right; +}; + +int depth(struct TreeNode *root) { + if (!root) + return 0; + else + return 1 + fmax(depth(root->left), depth(root->right)); +} + +bool isEvenOddTree(struct TreeNode *root) { + int d = depth(root); + struct TreeNode **q0 = malloc(50000 * sizeof(struct TreeNode *)); + struct TreeNode **q1 = malloc(50000 * sizeof(struct TreeNode *)); + int idx0 = 0, idx1 = 0; + q0[idx0] = root; + idx0 = 1; + while (idx0 || idx1) { + if (idx0) { + for (int i = 0; i < idx0; i++) { + if (!i) { + if (!(q0[i]->val % 2)) + return 0; + } else { + if (!(q0[i]->val % 2) || q0[i]->val <= q0[i - 1]->val) + return 0; + } + if (q0[i]->left) { + q1[idx1] = q0[i]->left; + idx1++; + } + if (q0[i]->right) { + q1[idx1] = q0[i]->right; + idx1++; + } + } + idx0 = 0; + } else { + for (int i = 0; i < idx1; i++) { + if (!i) { + if (q1[i]->val % 2 == 1) + return 0; + } else { + if (q1[i]->val % 2 == 1 || q1[i]->val >= q1[i - 1]->val) + return 0; + } + if (q1[i]->left) { + q0[idx0] = q1[i]->left; + idx0++; + } + if (q1[i]->right) { + q0[idx0] = q1[i]->right; + idx0++; + } + } + idx1 = 0; + } + } + return 1; +} |