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

简介: 【1115】Counting Nodes in a BST (30分)【BST建树 DFS】【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;   
}
相关文章
|
消息中间件 SQL JSON
自建MQTT迁移阿里云物联网平台指南
2020年是5G大规模商用的元年,使用阿里云物联网平台在产业爆发前打造一套安全可靠的业务架构,更能解放人力专注业务开发!
16312 0
|
存储 测试技术 数据处理
【计算机三级数据库技术】第2章 信息系统需求分析完整知识体系--附思维导图
本文详细介绍了信息系统需求分析的知识体系,包括需求分析的概念和意义、需求获取的方法、需求分析的过程,以及需求分析方法,如DFD数据流图、IDEF0、UML等。文章通过结构化分析和功能建模方法,帮助读者理解如何标识问题、建立需求模型、描述和确认需求,并比较了DFD与IDEF0两种方法的异同,同时提供了思维导图以辅助理解。
314 12
|
分布式数据库 流计算 Docker
实时计算 Flink版操作报错合集之在Docker上启动JobManager(JM)时遇到报错,,该怎么处理
在使用实时计算Flink版过程中,可能会遇到各种错误,了解这些错误的原因及解决方法对于高效排错至关重要。针对具体问题,查看Flink的日志是关键,它们通常会提供更详细的错误信息和堆栈跟踪,有助于定位问题。此外,Flink社区文档和官方论坛也是寻求帮助的好去处。以下是一些常见的操作报错及其可能的原因与解决策略。
|
机器学习/深度学习 存储 文字识别
OCR -- 文本识别 -- 实践篇
OCR -- 文本识别 -- 实践篇
533 1
|
存储 SQL 关系型数据库
【MySQL技术内幕】6.1-锁、lock和latch
【MySQL技术内幕】6.1-锁、lock和latch
271 0
|
SQL Apache 流计算
flink1.18发布与flink-cdc有重大相关调整吗?
flink1.18发布与flink-cdc有重大相关调整吗?
278 1
|
关系型数据库 MySQL Linux
Linux 命令 `db_upgrade` 详解与实战
`db_upgrade` 是一个自定义数据库升级命令,用于更新数据库结构和版本。它包括检查当前版本、备份、执行升级、更新版本信息和验证。基本语法是 `db_upgrade [OPTIONS]`,支持 `-b`(备份)、`-f`(强制升级)、`-v`(详细信息)等选项。在实战中,先备份数据库,然后使用 `db_upgrade` 命令升级,并验证结果。注意在生产环境升级前进行测试。虽然不是标准命令,但理解其用法有助于应对数据库升级。
|
存储 缓存 分布式计算
阿里云服务器2核8G、4核32G、8核64G配置最新收费标准和活动价格参考
2核8G、4核32G、8核64G配置的云服务器处理器与内存比为1:8,这种配比的云服务器一般适用于数据分析与挖掘,Hadoop、Spark集群和数据库,缓存等内存密集型场景,因此,多为企业级用户选择,目前用户购买2核16G配置活动价格最低为2439.24元/1年起,购买4核32G配置活动价格最低为4499.88元/1年起,购买8核64G配置活动价格最低为8621.16元/1年起,本文介绍这些配置的最新购买价格,包含原价收费标准和最新活动价格。
747 0
阿里云服务器2核8G、4核32G、8核64G配置最新收费标准和活动价格参考
|
网络安全 开发工具
Mac 端 iterm2 连接服务器 vim 串行的问题
Mac 端 iterm2 连接服务器 vim 串行的问题
|
存储 Python
Python字符串魔力:打造高效进销存系统的利器
Python字符串魔力:打造高效进销存系统的利器
118 0