1115 Counting Nodes in a BST（30 分）

先建树，之后BFS或者DFS都可以
BFS:

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
struct node {
    int data, layer;
    node *lchild, *rchild;
};
int n1, n2, lowest, above;
node* Newnode(int x)
{
    node* newnode = new node;
    newnode->data = x;
    newnode->lchild = newnode->rchild = NULL;
    return newnode;
}
void insert(node* &root, int x)
{
    if (root == NULL)
    {
        root = Newnode(x);
        return;
    }
    if (x <= root->data)insert(root->lchild, x);
    else if (x > root->data)insert(root->rchild, x);
}
int getheight(node* root)
{
    if (root == NULL)
    {
        return 0;
    }
    return max(getheight(root->lchild), getheight(root->rchild)) + 1;
}
void BFS(node* root)
{
    queue<node*>q;
    root->layer = 1;
    q.push(root);
    while (!q.empty())
    {
        node* front = q.front();
        if (front->layer == lowest)n1++;
        else if (front->layer == above)n2++;
        q.pop();
        if (front->lchild)
        {
            node* child = front->lchild;
            child->layer = front->layer + 1;
            q.push(child);
        }
        if (front->rchild)
        {
            node* child = front->rchild;
            child->layer = front->layer + 1;
            q.push(child);
        }
    }
}
int main()
{
    int n;
    scanf("%d", &n);
    node *root = NULL;
    for (int i = 0; i < n; i++)
    {
        int x;
        scanf("%d", &x);
        insert(root, x);
    }
    int h = getheight(root);
    lowest = h, above = h - 1;
    BFS(root);
    printf("%d + %d = %d", n1, n2, n1 + n2);
    return 0;
}

DFS:

//main里面写
DFS(root,1);
///////
void DFS(node* root, int h)
{
    if (root == NULL)return;
    if (h == lowest)n1++;
    if (h == above)n2++;
    if (root->lchild)DFS(root->lchild, h + 1);
    if (root->rchild)DFS(root->rchild, h + 1);
}