本文主要是介绍1115. Counting Nodes in a BST (30)[bst+dfs遍历]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1. 原题： https://www.patest.cn/contests/pat-a-practise/1115
2. 思路：
题意：
按照bst的原则构建bst树，然后输出倒数两层的结点数。
思路：
显然首先递归插入来建树。
然后树深可以用bfs或dfs。
dfs简捷些，然后递归的时候用一个计数器数组记录层深的结点数和最大树深就好了。
已AC。
按照bst的原则构建bst树，然后输出倒数两层的结点数。
思路：
显然首先递归插入来建树。
然后树深可以用bfs或dfs。
dfs简捷些，然后递归的时候用一个计数器数组记录层深的结点数和最大树深就好了。
已AC。
3. 源码：
#include<iostream>
using namespace std;struct Node
{Node() : left(NULL), right(NULL) {}int data;Node *left, *right;
};
Node *T = NULL;//bst树的根
int cnt[1000] = { 0 };//记录某深度所在层的结点数
int maxn = -1;//记录最大深度void Insert(Node *&t, int d);//构建bst树
void dfs(Node *nod, int deep);//递归获取树深并更新每层数目int main(void)
{//freopen("in.txt", "r", stdin);int N;scanf("%d", &N);for (int i = 0; i < N; i++){int elem;scanf("%d", &elem);Insert(T, elem);//建树}dfs(T, 0);//递归遍历printf("%d + %d = %d\n", cnt[maxn], cnt[maxn - 1], cnt[maxn] + cnt[maxn - 1]);return 0;
}void Insert(Node *&t, int d)//构建bst树, 注意参数是指针的指针（要修改指针)
{if (t == NULL)//递归结束条件{t = new Node;t->data = d;}else if (d <= t->data)//插入左侧Insert(t->left, d);else//插入右侧Insert(t->right, d);return;
}void dfs(Node *nod, int deep)//递归获取树深并更新每层数目
{if (nod == NULL)//递归终止return;dfs(nod->left, deep + 1);//递归左dfs(nod->right, deep + 1);//递归右cnt[deep]++;//累加if (deep > maxn)//更新最大树深maxn = deep;return;
}这篇关于1115. Counting Nodes in a BST (30)[bst+dfs遍历]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
