对给定数组所对应的二叉树依次完成前序,中序,后序遍历,并输出遍历结果。

本文主要是介绍对给定数组所对应的二叉树依次完成前序,中序,后序遍历,并输出遍历结果。,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

对给定数组所对应的二叉树依次完成前序,中序,后序遍历,并输出遍历结果。每行输入为一个二叉树,一维数组形式。其中-1表示Nil节点,例如:1,7,2,6,-1,4,8 构成的二叉树如下图所示:

在这里插入图片描述
结果以二维数组形式输出(前序,中序,后序遍历的结果),其中Nil节点不用输出。
时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 256M,其他语言512M

示例1
输入例子:
[1,7,2,6,-1,4,8]
输出例子:
[[1,7,6,2,4,8],[6,7,1,4,2,8],[6,7,4,8,2,1]]

例子说明:
注意二维数组中的结果依次为:前序,中序,后序遍历的结果,Nil(-1)节点不用输出。

算法步骤:

  • 首先,使用队列的方式创建二叉树;
  • 其次,对二叉树进行先序、中序、后序遍历,并保存值;
  • 最终,输出遍历结果;

#include <queue>
class Solution {public:/*** 对给定的二叉树依次完成前序,中序,后序遍历,并输出遍历结果* @param input int整型一维数组 -1表示Nil节点* @param inputLen int input数组长度* @return int整型vector<vector<>>*/typedef struct BTNode {int val;struct BTNode* lchild;struct BTNode* rchild;} BTNode;void createNode(BTNode*& node, int val) {node = (BTNode*)malloc(sizeof(BTNode));node->val = val;node->lchild = nullptr;node->rchild = nullptr;}void preorderTrval(BTNode* node, vector<int>& rs) {if (node != nullptr) {if (node->val != -1) {rs.push_back(node->val);}preorderTrval(node->lchild, rs);preorderTrval(node->rchild, rs);}}void inorderTrval(BTNode* node, vector<int>& rs) {if (node != nullptr) {inorderTrval(node->lchild, rs);if (node->val != -1) {rs.push_back(node->val);}inorderTrval(node->rchild, rs);}}void houorderTrval(BTNode* node, vector<int>& rs) {if (node != nullptr) {houorderTrval(node->lchild, rs);houorderTrval(node->rchild, rs);if (node->val != -1) {rs.push_back(node->val);}}}vector<vector<int>> binaryTreeScan(int* input, int inputLen) {vector<vector<int> > res;queue<BTNode*> qu;if (inputLen == 0) {return res;}BTNode* head;createNode(head, input[0]);qu.push(head);int index = 1;while (!qu.empty()) {BTNode* no = qu.front();if (index < inputLen) {createNode(no->lchild, input[index]);qu.push(no->lchild);}index++;if (index < inputLen) {createNode(no->rchild, input[index]);qu.push(no->rchild);}index++;qu.pop();}vector<int> re1;preorderTrval(head, re1);res.push_back(re1);re1.clear();inorderTrval(head, re1);res.push_back(re1);re1.clear();houorderTrval(head, re1);res.push_back(re1);return res;}
};

删除数组中的重复项

给定一个数组,你需要删除其中重复出现的元素,只保留最后一次出现的重复元素,使得每个元素只出现一次,返回新数组,并保证新数组中的元素顺序与原数组一致。

vector<int> removeDuplicate(int* array, int arrayLen) {map<int, int> us;for (int i = 0; i < arrayLen; i++) {us[array[i]] = i;}vector<pair<int, int>> vc;for (auto nums : us) {vc.push_back(pair{ nums.first,nums.second });}sort(vc.begin(), vc.end(), [&](pair<int, int> num1, pair<int, int> num2) {return num1.second < num2.second; });vector<int> res;for (auto vv : vc) {res.emplace_back(vv.first);}return res;}

这篇关于对给定数组所对应的二叉树依次完成前序,中序,后序遍历,并输出遍历结果。的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

hdu 1166 敌兵布阵(树状数组 or 线段树)

题意是求一个线段的和,在线段上可以进行加减的修改。 树状数组的模板题。 代码: #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while

顺序表之创建,判满,插入,输出

文章目录 🍊自我介绍🍊创建一个空的顺序表,为结构体在堆区分配空间🍊插入数据🍊输出数据🍊判断顺序表是否满了,满了返回值1,否则返回0🍊main函数 你的点赞评论就是对博主最大的鼓励 当然喜欢的小伙伴可以:点赞+关注+评论+收藏(一键四连)哦~ 🍊自我介绍   Hello,大家好,我是小珑也要变强(也是小珑),我是易编程·终身成长社群的一名“创始团队·嘉宾”

AI(文生语音)-TTS 技术线路探索学习:从拼接式参数化方法到Tacotron端到端输出

AI(文生语音)-TTS 技术线路探索学习:从拼接式参数化方法到Tacotron端到端输出 在数字化时代,文本到语音(Text-to-Speech, TTS)技术已成为人机交互的关键桥梁,无论是为视障人士提供辅助阅读,还是为智能助手注入声音的灵魂,TTS 技术都扮演着至关重要的角色。从最初的拼接式方法到参数化技术,再到现今的深度学习解决方案,TTS 技术经历了一段长足的进步。这篇文章将带您穿越时

Java 后端接口入参 - 联合前端VUE 使用AES完成入参出参加密解密

加密效果: 解密后的数据就是正常数据: 后端:使用的是spring-cloud框架,在gateway模块进行操作 <dependency><groupId>com.google.guava</groupId><artifactId>guava</artifactId><version>30.0-jre</version></dependency> 编写一个AES加密

leetcode105 从前序与中序遍历序列构造二叉树

根据一棵树的前序遍历与中序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如,给出 前序遍历 preorder = [3,9,20,15,7]中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树: 3/ \9 20/ \15 7   class Solution {public TreeNode buildTree(int[] pr

C语言:柔性数组

数组定义 柔性数组 err int arr[0] = {0}; // ERROR 柔性数组 // 常见struct Test{int len;char arr[1024];} // 柔性数组struct Test{int len;char arr[0];}struct Test *t;t = malloc(sizeof(Test) + 11);strcpy(t->arr,

C 语言基础之数组

文章目录 什么是数组数组变量的声明多维数组 什么是数组 数组,顾名思义,就是一组数。 假如班上有 30 个同学,让你编程统计每个人的分数,求最高分、最低分、平均分等。如果不知道数组,你只能这样写代码: int ZhangSan_score = 95;int LiSi_score = 90;......int LiuDong_score = 100;int Zhou

计算数组的斜率,偏移,R2

模拟Excel中的R2的计算。         public bool fnCheckRear_R2(List<double[]> lRear, int iMinRear, int iMaxRear, ref double dR2)         {             bool bResult = true;             int n = 0;             dou

C# double[] 和Matlab数组MWArray[]转换

C# double[] 转换成MWArray[], 直接赋值就行             MWNumericArray[] ma = new MWNumericArray[4];             double[] dT = new double[] { 0 };             double[] dT1 = new double[] { 0,2 };