根据前序和中序重建二叉树

本文主要是介绍根据前序和中序重建二叉树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

#include <iostream>
#include <vector>
#include <math.h>
#include <stdlib.h>#define N 100using namespace std;struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
}; TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {int vinsize = vin.size(), i, root=0;vector<int> preLeft, preRight, inLeft, inRight;if(vinsize == 0)return NULL;TreeNode *head = new TreeNode(pre[0]);//head = (TreeNode*)malloc(sizeof(TreeNode));//head->val   = pre[0];//head->left  = NULL;//head->right = NULL;for(i=0; i<vinsize; i++)if(vin[i] == pre[0]){root = i;break;	}for(i=0; i<root; i++){preLeft.push_back(pre[i+1]);inLeft.push_back(vin[i]);//preLeft[i] = pre[i+1];//inLeft[i] = vin[i];}       for(i=root+1; i<vinsize; i++){preRight.push_back(pre[i]);inRight.push_back(vin[i]);//preRight[i] = pre[i];//inRight[i] = vin[i];}//cout<<"Here...";head->left  = reConstructBinaryTree(preLeft, inLeft);head->right = reConstructBinaryTree(preRight, inRight); return head;}void preReverse(TreeNode * h){if(h == NULL)return;cout<< h->val << " ";preReverse(h->left);preReverse(h->right);
}int main(){vector<int> pre, in;int val1[] = {1,2,4,7,3,5,6,8} , val2[] = {4,7,2,1,5,3,8,6}, len;len = sizeof(val1)/sizeof(val1[0]);cout<<len<<endl;TreeNode *head = (TreeNode*)malloc(sizeof(TreeNode));for(int i=0; i<len;i++){pre.push_back(val1[i]);in.push_back(val2[i]);	}head = reConstructBinaryTree(pre, in);preReverse(head);return 0;
} 

这篇关于根据前序和中序重建二叉树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---