题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# 返回构造的TreeNode根节点
#采用递归的思想。根据前序遍历和中序遍历来构建二叉树的思路：前序遍历的第一个则是二叉树的根，
#找到根在中序遍历中的位置，则根将中序遍历分为了两部分，根的左边为二叉树的左子树，
#根的右边为二叉树的右子树，对应左右子树在可前序遍历中是连续存在的，
#根据该思路可以继续分别寻找左子树与右子树的根节点，递归进行。
#判断二叉树是否为空，进行长度的判断即可。
#还要注意将根定义成节点的形式。在进行本函数的递归调用时，需要在本函数名前面加上self.。
def reConstructBinaryTree(self, pre, tin):
# write code here
if len(pre) == 0:
return None
root_data = TreeNode(pre[0])
i=tin.index(pre[0])
root_data.left =self.reConstructBinaryTree(pre[1:1+i],tin[:i])
root_data.right =self.reConstructBinaryTree(pre[1+i:],tin[1+i:])
return root_data
#include <iostream>
#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
vector<int>pre_1;
vector<int>vin_1;
void build(TreeNode* node, int l1, int r1, int l2, int r2)
{
if (l1>r1 || l2>r2)
{
return;
}
int i, l_ans, r_ans;
int number = pre_1[l1];
for (i = l2; i <= r2; i++)
{
if (vin_1[i] == number)
{
break;
}
}
l_ans = i - l2;
r_ans = r2 - i;
if (l_ans > 0)
{
TreeNode* temp = (TreeNode*)malloc(sizeof(TreeNode));
temp->val = pre_1[l1 + 1];
temp->left = temp->right = NULL;
node->left = temp;
build(temp, l1 + 1, l1 + l_ans, l2, i - 1);
}
if (r_ans > 0)
{
TreeNode* temp = (TreeNode*)malloc(sizeof(TreeNode));
temp->val = pre_1[l1 + l_ans + 1];
temp->left = temp->right = NULL;
node->right = temp;
build(temp, l1 + l_ans + 1, r1, i + 1, r2);
}
}
TreeNode* reConstructBinaryTree(vector<int> pre, vector<int> vin)
{
TreeNode *head = NULL;
if (pre.size() == 0)
{
return head;
}
TreeNode* temp = (TreeNode*)malloc(sizeof(TreeNode));
temp->val = pre[0];
temp->left = temp->right = NULL;
head = temp;
pre_1 = pre;
vin_1 = vin;
build(head, 0, pre.size() - 1, 0, vin.size() - 1);
return head;
}
};
void display(TreeNode* node)
{
if (node == NULL)
{
return;
}
display(node->left);
display(node->right);
cout << node->val << " ";
}
int main()
{
TreeNode *c;
Solution s;
int a[15] = { 1, 2, 4, 7, 3, 5, 6, 8 };
int b[15] = { 4, 7, 2, 1, 5, 3, 8, 6 };
vector<int> pre(a, a + 8);
vector<int> vin(b, b + 8);
c = s.reConstructBinaryTree(pre, vin);
display(c);
cout << endl;
system("pause");
return 0;
}