二叉树的各种基本功！

#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);
}