leetcode

// 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;
}