PAT(甲级)1115 Counting Nodes in a BST(二叉搜索树遍历)

Description

题目大意:构建二叉搜索树：比左子节点大，比右子节点小，找到倒数第一层节点总数和倒数第二层节点总数

Input

n，接下来n个节点的数值

Output

输出最后一层和倒数第二层节点的个数，以及它们的和

解题思路

算法标签：二叉搜索树的遍历 构建二叉搜索树，levels统计该层节点的个数，maxdepth-1是该二叉搜索树的深度（之所以-1研究dfs函数去吧）

代码

//TSWorld #include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <cstring> #include <cmath> #include <vector> using namespace std; const int N = 10005; const int MAXX = 1314520; int levels[N]; int maxdepth; struct node { int key; struct node* left; struct node* right; }; struct node* BuiltTree(struct node *root,int key) { if(root == NULL) { root = new node(); //cout<<key<<endl; root->key = key; root->left = NULL; root->right = NULL; } else if(root->key < key) { root->right = BuiltTree(root->right,key); } else { root->left = BuiltTree(root->left,key); } return root; } void dfs(struct node* root,int depth) { if(root == NULL) { maxdepth = max(maxdepth,depth); return; } levels[depth]++; //遍历左子树 dfs(root->left,depth+1); //遍历右子树 dfs(root->right,depth+1); } int main() { int n = 0,data = 0; node* root = NULL; cin>>n; //cout<<n<<endl; for(int i=1;i<=n;i++) { scanf("%d",&data); //建立二叉搜索树 //cout<<data<<endl; root = BuiltTree(root,data); } //初始化最大深度为-1，根节点深度为0 maxdepth = -1; dfs(root,0); printf("%d + %d = %d",levels[maxdepth-1],levels[maxdepth-2],levels[maxdepth-1]+levels[maxdepth-2]); return 0; }