复习改进版

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

#define not !
#define and &&
#define or ||

#define ri register int
#define rep(inc, frm, to) for (ri inc = frm; inc < (to); ++inc)
#define rep2(inc, frm, to) for (ri inc = frm; inc > (to); --inc)

#define setbit(x, y) x |= 1 << y
#define clrbit(x, y) x &= ~(1 << y)
#define getbit(x, y) x >> y & 1
#define flipbit(x, y) x ^= 1 << y
#define show_bin(x) { rep2(i, 31, ~0) printf("%d%c", getbit(x, i), i ? 9 : 10); }

#define SWAP(a, b) { typeof(a) tmp = a; a = b; b = tmp; }

typedef long long int ll;
#define r() fast_read()

bool is_digit(const char c) {
  return c >= 48 and c <= 57;
}

ll my_pow(int base, int exponent) {
  return exponent ? my_pow(base, exponent - 1) * base : 1;
}

int gcd(int a, int b) {
  return b ? gcd(b, a % b) : a;
}

ll fast_read(void) {
  ll n = 0, sign = 1;
  char c = getchar();
  while (not is_digit(c)) {
    if (c == '-') sign = ~0;
    c = getchar();
  }
  while (is_digit(c)) {
    n = (n << 1) + (n << 3) + (c ^ 48);
    c = getchar();
  }
  return sign * n;
}

void swap(void* a, void* b, size_t size) {
  char *p = (char*) a, *q = (char*) b;
  rep(i, 0, size) *p ^= *q, *q ^= *p, *p++ ^= *q++;
}

void bubble_sort(void* base,
                 size_t num,
                 size_t size,
                 int (*compar) (const void*, const void*)) {

  rep(i, 0, num - 1) {
    bool exchange = 0;
    rep(j, 0, num - 1 - i) {
      if (compar(base + j * size, base + (j + 1) * size) > 0) {
        swap(base + j * size, base + (j + 1) * size, size);
        exchange = 1;
      }
    }
    if (not exchange) break;
  }
}

typedef struct TreeNode {
  int val;
  struct TreeNode* left;
  struct TreeNode* right;
} TreeNode, *PtrToNode;

// PtrToNode insertIntoBST(PtrToNode root, int val) {
//   if (not root) {
//     root = malloc(sizeof *root);
//     root->val = val;
//     root->left = root->right = NULL;
//     return root;
//   }
//   if (val <= root->val)
//     root->left = insertIntoBST(root->left, val);
//   else
//     root->right = insertIntoBST(root->right, val);

//   return root;
// }

void insertIntoBST(PtrToNode* root, int val) {
  if (not *root) {
    *root = malloc(sizeof **root);
    (*root)->val  = val;
    (*root)->left = (*root)->right = NULL;
    return;
  }
  if (val <= (*root)->val)
    insertIntoBST(&(*root)->left, val);
  else
    insertIntoBST(&(*root)->right, val);
}

void print_node(PtrToNode node) {
  printf("%d ", (*node).val);
}

// 二叉搜索树的中序的遍历序列一定是一个非单调递减序列
void inorder(PtrToNode root, void (*visit) (PtrToNode)) {
  if (not root) return;
  inorder(root->left, visit);
  visit(root);
  inorder(root->right, visit);
}

typedef PtrToNode QElemType;

// typedef int QElemType;

/* 循环队列的结构本声明  */
typedef struct {
  QElemType* base;
  size_t front, rear, capacity;
} SqQueue;

// ===================== SqQueue API =====================
bool InitQueue(SqQueue* Q, size_t capacity);

bool QueueEmpty(SqQueue* Q);

bool QueueFull(SqQueue* Q);

size_t QueueLength(SqQueue* Q);

bool EnQueue(SqQueue* Q, QElemType e);

bool DeQueue(SqQueue* Q, QElemType* e);

QElemType GetFront(SqQueue* Q);

// 第二版新增的API
QElemType GetRear(SqQueue* Q);

void CleanQueue(SqQueue* Q);

void DestroyQueue(SqQueue* Q);
// ===================== SqQueue API =====================

bool InitQueue(SqQueue* Q, size_t capacity) {
  assert(capacity > 0);

  Q->base = (QElemType*) malloc((capacity + 1) * sizeof(QElemType));
  if (!Q->base) {
    fprintf(stderr, "Failed to allocate the memory!\n");
    return false;
  }
  Q->front = Q->rear = 0;
  Q->capacity = capacity + 1;
  return true;
}

bool QueueEmpty(SqQueue* Q) {
  return Q->front == Q->rear;
}

bool QueueFull(SqQueue* Q) {
  return (Q->rear + 1) % Q->capacity == Q->front;
}

size_t QueueLength(SqQueue* Q) {
  return (Q->rear - Q->front + Q->capacity) % Q->capacity;
}

bool EnQueue(SqQueue* Q, QElemType e) {
  if (QueueFull(Q)) {
    fprintf(stderr, "The queue is full!\n");
    return false;
  }
  *(Q->base + Q->rear) = e;
  Q->rear = (Q->rear + 1) % Q->capacity;
  return true;
}

bool DeQueue(SqQueue* Q, QElemType* e) {
  if (QueueEmpty(Q)) {
    fprintf(stderr, "The queue is empty!\n");
    return false;
  }
  *e = *(Q->base + Q->front);
  Q->front = (Q->front + 1) % Q->capacity;
  return true;
}

QElemType GetFront(SqQueue* Q) {
  if (QueueEmpty(Q)) {
    fprintf(stderr, "The queue is empty!\n");
    return NULL;
  }
  return *(Q->base + Q->front);
}

QElemType GetRear(SqQueue* Q) {
  if (QueueEmpty(Q)) {
    fprintf(stderr, "The queue is empty!\n");
    return NULL;
  }
  return Q->base[(Q->rear - 1 + Q->capacity) % Q->capacity];
}

void CleanQueue(SqQueue* Q) {
  Q->front = Q->rear = 0;
}

void DestroyQueue(SqQueue* Q) {
  free(Q->base);
}

void BFS(PtrToNode root) {
  SqQueue Q;
  InitQueue(&Q, 520);
  EnQueue(&Q, root);

  int n1 = 0, n2 = 0;
  PtrToNode node; // current node pointer
  while (not QueueEmpty(&Q)) {
    size_t sz = QueueLength(&Q);
    n2 = n1, n1 = sz; // 两个滚动变量
    while (sz--) {
      DeQueue(&Q, &node);
      if (node->left)  EnQueue(&Q, node->left);
      if (node->right) EnQueue(&Q, node->right);
    }
  }

  printf("%d + %d = %d\n", n1, n2, n1 + n2);
  DestroyQueue(&Q);
}

signed main(int argc, char const *argv[]) {

  // freopen("test.in", "r", stdin);

  int n = r();
  PtrToNode root = NULL;
  while (n--) insertIntoBST(&root, r());

  // inorder(root, print_node);

  BFS(root);
  // fclose(stdin);
  return ~~(0 ^ 0);
}

二叉树的各种基本功！

#include <iostream>
#include <queue>

using namespace std;
int n, n1, n2;

struct TreeNode {
  int val;
  TreeNode *left, *right;
  TreeNode(int _val) : val(_val), left(nullptr), right(nullptr) {};
  ~TreeNode() {};
};

TreeNode* insertIntoBST(TreeNode* root, int val) {
  // recursion exit condition
  if (!root) return new TreeNode(val);
  if (val <= root->val)
    root->left = insertIntoBST(root->left, val);
  else if (val > root->val)
    root->right = insertIntoBST(root->right, val);
  return root;
}

void inOrder(TreeNode* root) {
  if (!root) return;
  inOrder(root->left);
  printf("%d ", root->val);
  inOrder(root->right);
}

int maxDepth(TreeNode* root) {
  return root ? 1 + max(maxDepth(root->left), maxDepth(root->right)) : 0;
}

int main(void) {
  scanf("%d", &n);

  TreeNode* root = nullptr;
  while (n--) {
    int val;
    scanf("%d", &val);
    root = insertIntoBST(root, val);
  }

  int depth = maxDepth(root);
  // inOrder(root);
  queue<TreeNode*> q{{root}};

  int level = 1;
  while (not q.empty()) {
    int sz = q.size();
    if (level == depth) n1 = sz;
    else if (level == depth - 1) n2 = sz;
    while (sz--) {
      auto cur = q.front(); q.pop();
      if (cur->left)  q.emplace(cur->left);
      if (cur->right) q.emplace(cur->right);
    }
    ++level;
  }

  printf("%d + %d = %d\n", n1, n2, n1 + n2);
}