昆山网站建设昆山,横沥网站制作招聘,企业家网站建设,2003 您的安全设置不允许网站使用安装题目如下#xff1a;
一个二叉树#xff0c;树中每个节点的权值互不相同。
现在给出它的后序遍历和中序遍历#xff0c;请你输出它的层序遍历。
输入格式
第一行包含整数 N#xff0c;表示二叉树的节点数。
第二行包含 N 个整数#xff0c;表示二叉树的后序遍历。
第…题目如下
一个二叉树树中每个节点的权值互不相同。
现在给出它的后序遍历和中序遍历请你输出它的层序遍历。
输入格式
第一行包含整数 N表示二叉树的节点数。
第二行包含 N 个整数表示二叉树的后序遍历。
第三行包含 N 个整数表示二叉树的中序遍历。
输出格式
输出一行 N 个整数表示二叉树的层序遍历。
数据范围
1≤N≤30, 官方并未给出各节点权值的取值范围为方便起见在本网站范围取为 1∼N。
输入样例
7
2 3 1 5 7 6 4
1 2 3 4 5 6 7输出样例
4 1 6 3 5 7 2 中序遍历遵循规则左根右1234567
后序遍历遵循规则左右根2315764
如题它的树长这样 可以得知后序遍历最后一个位置即为该树的根结点找到中序遍历中根结点位置即可判断出左子树与右子树结点个数即 4 为根结点值在中序遍历中其前面与后面各有 3 个节点因此 123为左子树各结点值567为右结点各结点值再递归到左子树与右子树重复该操作即可得到该树的结构 代码如下 #include iostream
#include vector
#include queue
using namespace std;const int N 35;//定义树结构
typedef struct TreeNode{int val;TreeNode* left;TreeNode* right;TreeNode(int value) : val(value), left(nullptr), right(nullptr) {} //构造函数
}TreeNode;//建立树结构
TreeNode* BuildTree(vectorint postorder, vectorint inorder, int postEnd, int inStart, int inEnd) {if(postEnd 0 || inStart inEnd)return nullptr;//找到根节点并开辟空间int rootval postorder[postEnd];TreeNode* root new TreeNode(rootval);//找到该根节点在中序遍历中的位置int rootIndexInInOrder 0;for(rootIndexInInOrder inStart; rootIndexInInOrder inEnd; rootIndexInInOrder){if(inorder[rootIndexInInOrder] rootval){break;}}//计算出右子树个数int rightTreeSize inEnd - rootIndexInInOrder;//递归左右子树root-right BuildTree(postorder, inorder, postEnd - 1, rootIndexInInOrder 1, inEnd);root-left BuildTree(postorder, inorder, postEnd - 1 - rightTreeSize, inStart, rootIndexInInOrder - 1);return root;
}//树的层序遍历
vectorint GetLevelOrderVal(TreeNode* root){vectorint res;if(!root) return res;queueTreeNode* q;q.push(root);while(!q.empty()){auto node q.front();q.pop();res.push_back(node-val);if(node-left) q.push(node-left);if(node-right) q.push(node-right);}return res;
}int main(){vectorint postorder(N);vectorint inorder(N);int n 0;cin n;for(int i 0; i n; i) cin postorder[i];for(int i 0; i n; i) cin inorder[i];TreeNode* root BuildTree(postorder, inorder, n - 1, 0, n - 1);vectorint res GetLevelOrderVal(root);for(auto val : res)cout val ;cout endl;return 0;
}
