1115 Counting Nodes in a Binary Search Tree(30分)

2023-11-05 13:28

本文主要是介绍1115 Counting Nodes in a Binary Search Tree(30分),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目翻译:

给定一组序列,请建立二叉搜索树

题解思路:

注意是二叉搜索树BST,而非平衡二叉树AVL,两者的区别如下:

  • BST:

  • AVL: 

因此只需要采用常规的建树手段即可,需要注意的是什么时候采用指针,什么时候不采用指针类型更好:

对于类似这种左右子树的值都已给出的话采用非指针建树更好(用一个结构体数组来存储)

而对于给定一串序列让你建立这个树(没有点明左右孩子关系的话),采用指针类型结构体更好:

代码:

#include<bits/stdc++.h>
using namespace std;
int N;
vector<int> lev[1001];struct node {int val = 0;node* left, *right;node() {left = nullptr;right = nullptr;}
};node* insert(node* root, int num, int curlev)
{if (root == nullptr){root = new node();root->val = num;lev[curlev].push_back(num);return root;}if (num <= root->val)root->left = insert(root->left, num, curlev + 1);elseroot->right = insert(root->right, num, curlev + 1);return root;
}int main()
{int temp;cin >> N ;node* root = nullptr;for (int i = 0;i < N;i++){cin >> temp;root = insert(root, temp, 0);}int result = 0;while (lev[result].size())result++;if (result == 1)cout << lev[result - 1].size() << " + " << 0 << " = " << lev[result - 1].size();elsecout << lev[result - 1].size() << " + " << lev[result - 2].size() << " = " << lev[result - 2].size() + lev[result - 1].size();
}

坑点:

注意测试点3,4可能是因为你的深度数组开太小了,最好开到1000+10

测试点5:注意可能是因为只有一层的缘故,所以倒数第二层为0

这篇关于1115 Counting Nodes in a Binary Search Tree(30分)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/350164

相关文章

HTML5 搜索框Search Box详解

《HTML5搜索框SearchBox详解》HTML5的搜索框是一个强大的工具,能够有效提升用户体验,通过结合自动补全功能和适当的样式,可以创建出既美观又实用的搜索界面,这篇文章给大家介绍HTML5... html5 搜索框(Search Box)详解搜索框是一个用于输入查询内容的控件,通常用于网站或应用程

基于Python实现一个Windows Tree命令工具

《基于Python实现一个WindowsTree命令工具》今天想要在Windows平台的CMD命令终端窗口中使用像Linux下的tree命令,打印一下目录结构层级树,然而还真有tree命令,但是发现... 目录引言实现代码使用说明可用选项示例用法功能特点添加到环境变量方法一:创建批处理文件并添加到PATH1

shell脚本自动删除30天以前的文件(最新推荐)

《shell脚本自动删除30天以前的文件(最新推荐)》该文章介绍了如何使用Shell脚本自动删除指定目录下30天以前的文件,并通过crontab设置定时任务,此外,还提供了如何使用Shell脚本删除E... 目录shell脚本自动删除30天以前的文件linux按照日期定时删除elasticsearch索引s

TP-Link PDDNS服将于务6月30日正式停运:用户需转向第三方DDNS服务

《TP-LinkPDDNS服将于务6月30日正式停运:用户需转向第三方DDNS服务》近期,路由器制造巨头普联(TP-Link)在用户群体中引发了一系列重要变动,上个月,公司发出了一则通知,明确要求所... 路由器厂商普联(TP-Link)上个月发布公告要求所有用户必须完成实名认证后才能继续使用普联提供的 D

mysql-8.0.30压缩包版安装和配置MySQL环境过程

《mysql-8.0.30压缩包版安装和配置MySQL环境过程》该文章介绍了如何在Windows系统中下载、安装和配置MySQL数据库,包括下载地址、解压文件、创建和配置my.ini文件、设置环境变量... 目录压缩包安装配置下载配置环境变量下载和初始化总结压缩包安装配置下载下载地址:https://d

30常用 Maven 命令

Maven 是一个强大的项目管理和构建工具,它广泛用于 Java 项目的依赖管理、构建流程和插件集成。Maven 的命令行工具提供了大量的命令来帮助开发人员管理项目的生命周期、依赖和插件。以下是 常用 Maven 命令的使用场景及其详细解释。 1. mvn clean 使用场景:清理项目的生成目录,通常用于删除项目中自动生成的文件(如 target/ 目录)。共性规律:清理操作

uva 575 Skew Binary(位运算)

求第一个以(2^(k+1)-1)为进制的数。 数据不大,可以直接搞。 代码: #include <stdio.h>#include <string.h>const int maxn = 100 + 5;int main(){char num[maxn];while (scanf("%s", num) == 1){if (num[0] == '0')break;int len =

2024网安周今日开幕,亚信安全亮相30城

2024年国家网络安全宣传周今天在广州拉开帷幕。今年网安周继续以“网络安全为人民,网络安全靠人民”为主题。2024年国家网络安全宣传周涵盖了1场开幕式、1场高峰论坛、5个重要活动、15场分论坛/座谈会/闭门会、6个主题日活动和网络安全“六进”活动。亚信安全出席2024年国家网络安全宣传周开幕式和主论坛,并将通过线下宣讲、创意科普、成果展示等多种形式,让广大民众看得懂、记得住安全知识,同时还

AI基础 L9 Local Search II 局部搜索

Local Beam search 对于当前的所有k个状态,生成它们的所有可能后继状态。 检查生成的后继状态中是否有任何状态是解决方案。 如果所有后继状态都不是解决方案,则从所有后继状态中选择k个最佳状态。 当达到预设的迭代次数或满足某个终止条件时,算法停止。 — Choose k successors randomly, biased towards good ones — Close

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L