本题来自《剑指offer》 重构二叉树
题目：
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
思路：
二叉树的前序遍历：根左右，第一个值是根节点
二叉树的中序遍历：左根右，根节点的值在中间，左子树的节点在根的左边，右子树的节点在根的右边
首先找到前序的根节点，继而对应到中序中，分离出中序的根左、右子树。
其次对中序的左右子树，对应的找到前序的左右子树。
左、右子树同样是数，所以采用递归的思路进行遍历。
终止条件，当前序只有一个值时候，便是根节点，当没有值就返回None。
C++ Code：（未调通，栈溢出，是边界条件没有调好，后期改）
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
if (pre.size() == ){ //当前序为空时候，返回为空
return NULL;
}else if(pre.size() == ){ //当只有一个元素时候，便直接是根节点
TreeNode* root = new TreeNode(pre[]);
return root;
}else{
std::vector<int> vin_left,vin_right,pre_left,pre_right; //定义前序和中序的左右子节点
for (int i = ;vin[i]!=pre[];i++){ //中序的左节点
vin_left.push_back(vin[i++]);
}
for (int i = vin_left.size()+;i<vin.size();i++){ //中序的右子节点
vin_right.push_back(vin[i]);
}
for (int i = ;i<vin_left.size();i++){ //前序的左子节点
pre_left.push_back(pre[i]);
}
for (int i = pre_left.size()+;i<pre.size();i++){ //前序的右子节点
pre_right.push_back(pre[i]);
}
TreeNode* root = new TreeNode(pre[]); //构造根节点，其值就是前序的第一个值
root->left = reConstructBinaryTree(pre_left,vin_left); //左节点是递归的调用，前左子节点和中左子节点
root->right = reConstructBinaryTree(pre_right,vin_right);//右节点是递归的调用，前右子节点和中右子节点
return root; //将其返回
} }
};
Python Code：
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# 返回构造的TreeNode根节点
def reConstructBinaryTree(self, pre, tin):
# write code here
if len(pre) == 0: #当数据中没有数据返回None
return None
elif len(pre) == 1: #当前序中只有一个数时，则为根节点，直接返回
return TreeNode(pre[0])
else:
tin_left = tin[:tin.index(pre[0])] #中序的左子树为从头到前序的根节点
tin_right = tin[tin.index(pre[0])+1:] #中序的右子树为从根节点到尾部全部
pre_left = pre[1:len(tin_left)+1] #前序的左子树为从根节点开始到中序的左子树
pre_right = pre[len(tin_left)+1:] #前序的右子树为中序的右子树
res = TreeNode(pre[0]) #定义根节点
res.left = Solution.reConstructBinaryTree(self,pre_left,tin_left) #递归的调用左子树
res.right = Solution.reConstructBinaryTree(self,pre_right,tin_right)#递归的调用右子树
return res #最终返回根节点
# -*- coding: utf-8 -*-
"""
Created on Mon Apr 8 14:18:46 2019 @author: Administrator
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。 思路：
前序的第一个为根节点，依次找到其左节点的放在一起，右节点的放在一起，递归计算
""" class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
# 返回构造的TreeNode根节点
def reConstructBinaryTree(self, pre, tin):
# write code her
if len(pre) == 0: #如果没有节点就直接返回None
return None
elif len(pre) == 1: #如果只有一个节点就直接是头结点了，直接返回
return TreeNode(pre[0])
else:
tin_left = tin[:tin.index(pre[0])] #截取中左区域
tin_right = tin[tin.index(pre[0])+1:] #截取中右区域
pre_left = pre[1:len(tin_left)+1] #截取前左区域
pre_right = pre[len(tin_left)+1:] #截取前右区域
res = TreeNode(pre[0]) #头结点为前的第0个节点
res.left = Solution.reConstructBinaryTree(self,pre_left,tin_left) #递归，左节点是前左和中左
res.right = Solution.reConstructBinaryTree(self,pre_right,tin_right)#递归，右节点是前右和中右
return res
#前序遍历
def preorder(self,node):
if node:
print(node.val)
Solution.preorder(self,node.left)
Solution.preorder(self,node.right)
# 中序遍历
def inorder(self,node):
if node:
Solution.inorder(self,node.left)
print(node.val)
Solution.inorder(self,node.right)
#后序遍历
def postorder(self,node):
if node:
Solution.postorder(self,node.left)
Solution.postorder(self,node.right)
print(node.val)
if __name__ == '__main__':
pre = [1,2,4,7,3,5,6,8]
tin = [4,7,2,1,5,3,8,6]
solution = Solution()
tree = solution.reConstructBinaryTree(pre,tin)
solution.preorder(tree)
总结：
发现规律，终止和其实条件。