基于层序+中序遍历序列构建二叉树

2019-11-06 08:49:34

字体：大中小

来源：转载

供稿：网友

@算法学习

问题是：基于层序遍历序列+中序遍历序列唯一建立一棵树，然后输出前序，后序遍历序列。

四种遍历树的思路以及代码自然不必多言，有趣的是如何由层序+中序建立树。

首先需要说的是，这个也是递归解法。

http://paste.Ubuntu.com/24084585/

既然是递归解法，就需要想当前层的问题，给定一个层序遍历序列+中序遍历序列，当前能确定的根结点就是层序序列的第一个值，拿这个去在中序中找到根结点的下标k，就划分出来了左右子树。现在问题就有意思了，左子树在层序中的序列不是在一团的，而是散开的，换句话说，左子树的和右子树的层序遍历序列是交叉在一起的，怎么办？

我们想，如果能够有左子树的层序遍历序列和右子树的层序遍历序列就好了。

这个其实是非常漂亮的观点，基于这个就能够解决问题。

开两个数组专门存左右子树的遍历序列即可。

我重写的一个版本：

#include <stdio.h>#include <vector>#include <queue>using namespace std;const int maxn = 40;int in[maxn];vector<int> layer;vector<int> PRe,post; // 先存再输出也行，但是耗费一点时间struct node{ int data; node* left; node* right;};node* newNode(int val){ node* Node = new node; Node->left = NULL; Node->right = NULL; Node->data = val; return Node;}void preOrder(node* root){ if(!root) return; pre.push_back(root->data); preOrder(root->left); preOrder(root->right);}void postOrder(node* root){ if(!root) return; postOrder(root->left); postOrder(root->right); post.push_back(root->data);}node* createFromLevelInOrder(vector<int> layer, int inL, int inR){ if(layer.size() == 0) // 如果层序用完了，表示递归边界，可以往回归 { return NULL; } // 处理当前层的问题 node* root = newNode(layer[0]); int k; //在中序中划分 for(k = inL; k <= inR; k++) { if(layer[0] == in[k]) { break; //找到就跳出循环 } } vector<int> leftLayer; // 左子树层序遍历序列 vector<int> rightLayer; // 右子树层序遍历序列 for(int i = 1; i < layer.size(); i++) // 遍历当前层序，划分左右存储起来 { bool isLeft = false; for(int j = inL; j < k; j++) { if(layer[i] == in[j]) { isLeft = true; break; //确定一个就跳出来，当前是在外层的大循环下 } } if(isLeft) { leftLayer.push_back(layer[i]); } else { rightLayer.push_back(layer[i]); } } // 尤其需要注意这里需要用root的左右指针去接下一层的构造 root->left = createFromLevelInOrder(leftLayer,inL, k - 1); root->right = createFromLevelInOrder(rightLayer,k + 1, inR); return root;}int main(){ int n; scanf("%d", &n); int temp; // 控制输入 for(int i = 0; i < n; i++) { scanf("%d", &temp); layer.push_back(temp); //输入层序遍历序列 } for(int i = 0; i < n; i++) { scanf("%d", &in[i]); // 输入中序遍历序列 } node* root = createFromLevelInOrder(layer,0,n - 1); preOrder(root); postOrder(root); // 控制输出 for(int i = 0; i < pre.size(); i++) { printf("%d", pre[i]); if(i < pre.size() - 1) { printf(" "); } } printf("/n"); for(int i = 0; i < post.size(); i++) { printf("%d", post[i]); if(i < post.size() - 1) { printf(" "); } } printf("/n"); return 0;}

上一篇：嵌入式面试题——ARM试题（一）

下一篇：2月英语--感谢没有放弃