[数据结构与算法]按bst填充二叉树并层次遍历——PAT (Advanced Level) 1115 Counting Nodes in a BST (30 分)

题目概述：
按既定数组顺序填充一颗二叉树，并输出最低两层的个数

题目分析：
1。建立node结构体

struct node
{
    int val = inf;
    node *left = NULL;
    node *right = NULL;
};

2.学会用new node()

node* root = new node();

3.insert的话参数为node* root和int x
若该root无数，填充；
若有，若x小于等于当前数，insert左子树（若左子树为空来个new）
若x大于当前数，insert右子树（若右子树为空来个new）

void insert(node* root, int x)
{
    if(root->val == inf)
    {
        root->val = x;
        return;
    }
    else if(x <= root->val) 
    { 
        if(root->left == NULL) root->left = new node();
        insert(root->left, x);
    }
    else
    {
        if(root->right == NULL) root->right = new node();
        insert(root->right, x);        
    }
}

完整代码：

#include<bits/stdc++.h>
using namespace std;

vector<int> v;
int n;
const int inf = 99999999;

struct node
{
    int val = inf;
    node *left = NULL;
    node *right = NULL;
};

void insert(node* root, int x)
{
    if(root->val == inf)
    {
        root->val = x;
        return;
    }
    else if(x <= root->val) 
    { 
        if(root->left == NULL) root->left = new node();
        insert(root->left, x);
    }
    else
    {
        if(root->right == NULL) root->right = new node();
        insert(root->right, x);        
    }
}


int main()
{
    cin >> n;
    v.resize(n);
    for(int i = 0; i < n; i++) cin >> v[i];
    node* root = new node();
    for(int i = 0; i < n; i++) insert(root, v[i]);
    //cout << root->left->right->right->val;
    queue<node*> q;
    vector<int> cnt;
    q.push(root);
    while(!q.empty())
    {
        int len = q.size();
        cnt.push_back(len);
        for(int i = 0; i < len; i++)
        {
            node* temp = q.front();
            if(temp->left != NULL) q.push(temp->left);
            if(temp->right != NULL) q.push(temp->right);
            q.pop();
        }
    }
    printf("%d + %d = %d\n", cnt[cnt.size() - 1], cnt[cnt.size() - 2], cnt[cnt.size() - 1] + cnt[cnt.size() - 2]);
    return 0;
}

总结：
node结构体中两个node*
node* root = new node()
关键就是这个node的指针怎么建立