【1115】Counting Nodes in a BST (30分)【BST建树 DFS】

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<algorithm>  
#include<map>
#include<vector>
#include<queue> 
using namespace std;  
/*链表存储---递归建BST---DFS,传入的参数为结点和depth*/
/*若当前结点为NULL则更新maxdepth并return，数组sum存每层对应结点数*/
struct node{
  int data;
  struct node *left,*right;
};
void insert(node* &root,int data){
  if(root == NULL){//空树，说明查找失败，也即插入位置
    root=new node; //申请一个node结构体地址空间
    root->data=data;
    root->left=root->right=NULL;//初始无左右孩子
    return;
  }//一定要注意下面这个if是小于等于！！有等于情况
  if(data<=root->data) insert(root->left,data);//插在左子树
  else insert(root->right,data);//插在右子树
}
vector<int> num(1000);
int maxdepth=-1;
void dfs(node *root,int depth){
  if(root ==NULL){
    maxdepth=max(depth,maxdepth);
    return;
  }
  num[depth]++;//每访问一个结点就在这对应层的节点数加1
  dfs(root->left,depth+1);
  dfs(root->right,depth+1);
}
int main(){   
  int n,data;
  node* root=NULL;//定义头结点
  scanf("%d",&n);//结点个数
  for(int i=0;i<n;i++){
    scanf("%d",&data);
    insert(root,data);//将data插入树中
  }
  dfs(root,0);
  printf("%d + %d = %d",num[maxdepth-1] , num[maxdepth-2] , num[maxdepth-1]+num[maxdepth-2]);
  system("pause");
    return 0;   
}