aboutsummaryrefslogtreecommitdiff
path: root/even_odd_tree.c
diff options
context:
space:
mode:
Diffstat (limited to 'even_odd_tree.c')
-rw-r--r--even_odd_tree.c76
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;
+}