10.6( 105. 从前序与中序遍历序列构造二叉树 106. 从中序与后序遍历序列构造二叉树 )

2024-03-30 01:32

本文主要是介绍10.6( 105. 从前序与中序遍历序列构造二叉树 106. 从中序与后序遍历序列构造二叉树 ),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

105. 从前序与中序遍历序列构造二叉树(通过)

思路:递归构造
效率:86.85%
程序代码(完整版):
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<sstream>
#include<stack>//引入数据结构堆栈
using namespace std;
//105. 从前序与中序遍历序列构造二叉树
//思路:递归struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}};class Solution {public:TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {int n = preorder.size();return Haha(0, n-1, preorder, 0, n-1,inorder);}TreeNode* Haha(int a, int b, vector<int>& preorder, int c, int d, vector<int>& inorder) {if (a > b) return NULL;else {TreeNode* root = new TreeNode(preorder[a]);//首先创建一个根部节点int a1, b1, c1, d1, a2, b2, c2, d2;for (int i = c; i <= d; i++) {if (inorder[i] == preorder[a]) {a1 = a + 1;b1 = a + i - c;c1 = c;d1 = i - 1;a2 = a + i - c + 1;b2 = b;c2 = i + 1;d2 = d;}}root->left = Haha(a1, b1, preorder, c1, d1, inorder);root->right = Haha(a2, b2, preorder, c2, d2, inorder);return root;}}};void Traverse(vector<int> &result,TreeNode *root) {if (root == NULL);//这属于什么也不干else {result.push_back(root->val);Traverse(result,root->left);Traverse(result,root->right);}}int main() {Solution bb;int n;cin >> n;vector<int> a(n);vector<int> b(n);for (int i = 0; i < n; i++) {cin >> a[i] >> b[i];}TreeNode *root = bb.buildTree(a,b);vector<int> result;Traverse(result,root);for (int i = 0; i < n; i++) {cout << result[i];}return 0;}

前序遍历:根左右
中序遍历:左根右
后序遍历:左右根

106. 从中序与后序遍历序列构造二叉树

思路:和上面题目的思路一样
效率:79.52%
程序代码:
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<sstream>
#include<stack>//引入数据结构堆栈
using namespace std;
//105. 从前序与中序遍历序列构造二叉树
//思路:递归struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}};class Solution {public:TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {int n = postorder.size();return Haha(0, n-1, postorder, 0, n-1,inorder);}TreeNode* Haha(int a, int b, vector<int>& postorder, int c, int d, vector<int>& inorder) {if (a > b) return NULL;else {TreeNode* root = new TreeNode(postorder[b]);//首先创建一个根部节点int a1, b1, c1, d1, a2, b2, c2, d2;for (int i = c; i <= d; i++) {if (inorder[i] == postorder[b]) {a1 = a;b1 = a+i-1-c;c1 = c;d1 = i - 1;a2 = b+i-d;b2 = b-1;c2 = i + 1;d2 = d;}}root->left = Haha(a1, b1, postorder, c1, d1, inorder);root->right = Haha(a2, b2, postorder, c2, d2, inorder);return root;}}};void Traverse(vector<int> &result,TreeNode *root) {if (root == NULL);//这属于什么也不干else {result.push_back(root->val);Traverse(result,root->left);Traverse(result,root->right);}}int main() {Solution bb;int n;cin >> n;vector<int> a(n);vector<int> b(n);for (int i = 0; i < n; i++) {cin >> a[i] >> b[i];}TreeNode *root = bb.buildTree(a,b);vector<int> result;Traverse(result,root);for (int i = 0; i < n; i++) {cout << result[i];}return 0;}
补充知识点:

关于map和makepair,最快的方法使用的有map何makepair,用时8ms,而我的程序用时16ms,大家的思路整体上其实是差不多的。

最好的程序如下:
/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:
TreeNode* iterBuild(vector<int>& inorder, int is, int ie,vector<int>& postorder, int ps, int pe, unordered_map<int ,int> &mapList)
{if(is > ie || ps>pe)return NULL;int ri = mapList[postorder[pe]];TreeNode * root = new TreeNode(postorder[pe]);root->left = iterBuild(inorder, is, ri-1, postorder, ps, ps+ri-is-1, mapList);root->right = iterBuild(inorder, ri+1, ie, postorder, ps+ri-is, pe-1, mapList);return root;
}TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder)
{if(inorder.size()!=postorder.size() || !inorder.size() || !postorder.size())return NULL;unordered_map<int ,int> mapList;for(int i=0; i<inorder.size(); i++)mapList.insert(make_pair(inorder[i], i));return iterBuild(inorder, 0, inorder.size()-1, postorder, 0, postorder.size()-1, mapList);
}
};

所以,map其实就相当于是使中序遍历序列的元素和下标一一对应,是一个一对一的hash表,不需要再使用for循环依次寻找。节省了时间。

这篇关于10.6( 105. 从前序与中序遍历序列构造二叉树 106. 从中序与后序遍历序列构造二叉树 )的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

uva 10131 最长子序列

题意: 给大象的体重和智商,求体重按从大到小,智商从高到低的最长子序列,并输出路径。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vect

POJ1631最长单调递增子序列

最长单调递增子序列 import java.io.BufferedReader;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWriter;import java.math.BigInteger;import java.util.StringTokenizer;publ

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

PHP实现二叉树遍历(非递归方式,栈模拟实现)

二叉树定义是这样的:一棵非空的二叉树由根结点及左、右子树这三个基本部分组成,根据节点的访问位置不同有三种遍历方式: ① NLR:前序遍历(PreorderTraversal亦称(先序遍历)) ——访问结点的操作发生在遍历其左右子树之前。 ② LNR:中序遍历(InorderTraversal) ——访问结点的操作发生在遍历其左右子树之中(间)。 ③ LRN:后序遍历(PostorderT

day-50 求出最长好子序列 I

思路 二维dp,dp[i][h]表示nums[i] 结尾,且有不超过 h 个下标满足条件的最长好子序列的长度(0<=h<=k),二维数组dp初始值全为1 解题过程 状态转换方程: 1.nums[i]==nums[j],dp[i,h]=Math.max(dp[i,h],dp[j,h]+1) 2.nums[i]!=nums[j],dp[i,h]=Math.max(dp[i,h],dp[j,h-1

LeetCode:3177. 求出最长好子序列 II 哈希表+动态规划实现n*k时间复杂度

3177. 求出最长好子序列 II 题目链接 题目描述 给你一个整数数组 nums 和一个非负整数k 。如果一个整数序列 seq 满足在下标范围 [0, seq.length - 2] 中 最多只有 k 个下标i满足 seq[i] != seq[i + 1] ,那么我们称这个整数序列为好序列。请你返回 nums中好子序列的最长长度。 实例1: 输入:nums = [1,2,1,1,3],

react笔记 8-17 属性绑定 class绑定 引入图片 循环遍历

1、绑定属性 constructor(){super()this.state={name:"张三",title:'我是一个title'}}render() {return (<div><div>aaaaaaa{this.state.name}<div title={this.state.title}>我是一个title</div></div></div>)} 绑定属性直接使用花括号{}   注

用Python实现时间序列模型实战——Day 14: 向量自回归模型 (VAR) 与向量误差修正模型 (VECM)

一、学习内容 1. 向量自回归模型 (VAR) 的基本概念与应用 向量自回归模型 (VAR) 是多元时间序列分析中的一种模型,用于捕捉多个变量之间的相互依赖关系。与单变量自回归模型不同,VAR 模型将多个时间序列作为向量输入,同时对这些变量进行回归分析。 VAR 模型的一般形式为: 其中: ​ 是时间  的变量向量。 是常数向量。​ 是每个时间滞后的回归系数矩阵。​ 是误差项向量,假

时间序列|change point detection

change point detection 被称为变点检测,其基本定义是在一个序列或过程中,当某个统计特性(分布类型、分布参数)在某时间点受系统性因素而非偶然因素影响发生变化,我们就称该时间点为变点。变点识别即利用统计量或统计方法或机器学习方法将该变点位置估计出来。 Change Point Detection的类型 online 指连续观察某一随机过程,监测到变点时停止检验,不运用到

C++中类的构造函数调用顺序

当建立一个对象时,首先调用基类的构造函数,然后调用下一个派生类的 构造函数,依次类推,直至到达派生类次数最多的派生次数最多的类的构造函数为止。 简而言之,对象是由“底层向上”开始构造的。因为,构造函数一开始构造时,总是 要调用它的基类的构造函数,然后才开始执行其构造函数体,调用直接基类构造函数时, 如果无专门说明,就调用直接基类的默认构造函数。在对象析构时,其顺序正好相反。