这是一个非常经典的问题，一个二叉树通过其前序遍历和中序遍历可以唯一的确定一个二叉树，或者是通过后序和中序也可以唯一的确定二叉树，但是要注意前序+后序是不可以唯一的确定二叉树的。
变种问题：重建是返回树的根节点即可，但是有的会要求写出后序遍历序列。
重建二叉树的分析：首先根据前序遍历，第一个值就是根， 通过扫描中序的值，找到根，左边为左子树，右面的序列为右子树，可以递归求解。
解法一：较简单的解法
# -*- 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):
if len(pre) == 0:
return None
if len(pre) == 1:
return TreeNode(pre[0])
root = pre[0]
i = 0
while i < len(tin) and tin[i] != root:
i += 1
rootNode = TreeNode(root)
rootNode.left = self.reConstructBinaryTree(pre[1:i+1], tin[0:i])
rootNode.right = self.reConstructBinaryTree(pre[i+1:], tin[i+1:])
return rootNode
解法二：书里的方法：
# -*- 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
def constructTree(pre, tin, startPreorder, endPreorder, startInorder, endInorder):
rootValue = pre[startPreorder]
root = TreeNode(rootValue)
if startPreorder == endPreorder and startInorder == endInorder:
return root
rootInorder = startInorder
while(rootInorder <= endInorder and tin[rootInorder] != rootValue):
rootInorder += 1
leftLength = rootInorder - startInorder
leftPreorderEnd = leftLength + startPreorder
if leftLength > 0:
root.left = constructTree(pre, tin, startPreorder+1, leftPreorderEnd, startInorder, rootInorder -1)
if leftLength<(endPreorder - startPreorder):
root.right = constructTree(pre, tin, leftPreorderEnd+1, endPreorder,rootInorder+1, endInorder)
return root
return constructTree(pre, tin, 0, len(pre)-1, 0, len(pre) -1)
总结：根据前序先找到根节点---》根据中序找到左右子树---》递归
c++ :用递归的方法
/**
* 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.empty() || vin.empty() ) return NULL;
return helper(pre, vin, 0, pre.size() - 1, 0, vin.size() - 1);
}
TreeNode * helper(vector<int> pre, vector<int> vin, int pre_l, int pre_r, int vin_l, int vin_r){
if(pre_l > pre_r || vin_l > vin_r) return NULL;
int root_val = pre[pre_l];
TreeNode * root = new TreeNode(root_val);
int index = 0;
for(int i = vin_l; i <= vin_r; i++){
if(vin[i] == root_val) index = i;
}
int length = index - vin_l;
root->left = helper(pre, vin, pre_l + 1, pre_l + length, vin_l,vin_l + length - 1 );
root->right = helper(pre, vin, pre_l + length + 1, pre_r, vin_l + length + 1, vin_r);
return root;
}
};
/**
* 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.empty() || vin.empty() ) return NULL;
return helper(pre, vin, 0, pre.size() - 1, 0, vin.size() - 1);
}
TreeNode * helper(vector<int> pre, vector<int> vin, int pre_l, int pre_r, int vin_l, int vin_r){
if(pre_l > pre_r || vin_l > vin_r) return NULL;
int root_val = pre[pre_l];
TreeNode * root = new TreeNode(root_val);
int index = 0;
for(int i = vin_l; i <= vin_r; i++){
if(vin[i] == root_val) index = i;
}
int length = index - vin_l;
cout<<index<<endl;
root->left = helper(pre, vin, pre_l + 1, pre_l+length, vin_l,index - 1 );
//要注意index是vin中的下标，不是pre中的，所以与pre相关的都不可出现index
root->right = helper(pre, vin, pre_l + length + 1, pre_r, index + 1, vin_r);
return root;
}
};
