当前位置：首页 > news >正文

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

news 来源：原创 2024/9/20 16:51:08

对给定数组所对应的二叉树依次完成前序，中序，后序遍历，并输出遍历结果。每行输入为一个二叉树，一维数组形式。其中-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;}