首页 > 代码库 > 重建二叉树
重建二叉树
题目描述
输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。
基本思想:在中序序列中找到根节点的位置,根结点左边是左子树,右边是右子树。然后分别对左子树和右子树进行递归处理。
在打印树的函数上,我的实现方法是广度优先遍历,也就是按层打印二叉树。
#include <iostream> #include <algorithm> #include "string.h" #include "stdio.h" #include <vector> #include <deque> #include <stack> #include <queue> #include<map> #include<utility> #include "math.h" using namespace std; struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; class Tree{ public: void PrintTree(TreeNode* pRoot) { if(pRoot == NULL) return; int level = 0; int index = 0; int globle = 0; queue<TreeNode*> queue; queue.push(pRoot); while(!queue.empty()) { TreeNode* pNode = queue.front(); cout<<pNode->val<<" "; queue.pop(); if(pNode->left) { queue.push(pNode->left); } if(pNode->right) { queue.push(pNode->right); } } } }; class Solution { public: TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) { if(pre.size() == NULL || pre.size() == NULL || pre.size()!=vin.size()) return NULL; vector<int> pre_left; vector<int> pre_right; vector<int> vin_left; vector<int> vin_right; int index = 0; for(int i=0;i<vin.size();i++) { if(vin[i] == pre[0]) { index = i; break; } } for(int i=0;i<vin.size();i++) { if(i<index) { vin_left.push_back(vin[i]); pre_left.push_back(pre[i+1]); } if(i>index) { vin_right.push_back(vin[i]); pre_right.push_back(pre[i]); } } TreeNode* pRoot = new TreeNode(pre[0]); pRoot->left = reConstructBinaryTree(pre_left,vin_left);//递归左子树 pRoot->right = reConstructBinaryTree(pre_right,vin_right);//递归右子树 return pRoot; } }; int main() { vector<int> pre; pre.push_back(1); pre.push_back(2); pre.push_back(4); pre.push_back(7); pre.push_back(3); pre.push_back(5); pre.push_back(6); pre.push_back(8); vector<int> vin; vin.push_back(4); vin.push_back(7); vin.push_back(2); vin.push_back(1); vin.push_back(5); vin.push_back(3); vin.push_back(8); vin.push_back(6); Solution solution; Tree tree; TreeNode* p = solution.reConstructBinaryTree(pre,vin); tree.PrintTree(p); }
重建二叉树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。