输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
第一次看到这个题目感觉：这种题还能编程写出来，这不是某些面试的题目吗，根据指定的二叉树遍历顺序（前中，后中）确定二叉树的结构。让自己在纸上自己看看还行，编程怎么写呢，在纸上画了画，首先没有想到递归的方式，本想通过两个for循环，外面的循环是前序数组，里面的是中序，前序确定根节点比较容易，比如1是树的根节点，那2是根的左子树还是右子树呢，仅仅根据前序是无法判断的，这时候要根据中序，2在1的左边，所以2是1的左子树根节点，但是始终没有考虑好一个完整的步骤。后来开始想到了递归，因为树就是一个递归结构。
首先可以判定1是根节点所以可以将上述的两个序列分成4部分：
前序:[2,4,7]和[3,5,6,8]
中序: [4,7,2]和[5,3,8,6]
然后右 [2,4,7]和[4,7,2]构建新的树作为根节点的左子树，因为这些点在中序中位于1的左边。同理[3,5,6,8]和[5,3,8,6]构建根节点的右子树。
可以很容易看到除了数组范围变小了，其他的求解过程依旧没有变，前序的第一个元素的依然是构建的树的根节点。其他分割策略完全相同。
为了方便本地测试，代码使用了swift(题目在线测评网站上没有提供swift语言解题的功能，但是这个算法和语言是无关的)。
class TreeNode {
var val:Int!
var left:TreeNode?
var right:TreeNode?
init(val:Int) {
self.val = val
}
}
func reConstruct(pre:[Int],vin:[Int]) -> TreeNode? {
//为0表示树是空的
if pre.count==0&&vin.count==0 {
return nil
}
//根节点在中序的位置
let r_idx = vin.index(of: pre[0]);
//前序的第一个就是树的根节点
let root = TreeNode(val: pre[0]);
var sub_left_pre = [Int]()
var sub_right_pre = [Int]()
for val in pre {
//前序中位于根节点之前的中序的值，作为根节点的左子树的前序序列，否则作为右子树的前序序列
if vin.index(of: val)! < r_idx! {
sub_left_pre.append(val)
}
else if vin.index(of: val)! > r_idx!{
sub_right_pre.append(val)
}
}
var sub_left_in = [Int]()
var sub_right_in = [Int]()
for (i,val) in vin.enumerated() {
//中序里面，根节点之前的元素序列作为左子树的中序序列，之后的作为右子树序列
if i < r_idx! {
sub_left_in.append(val)
}
else if i > r_idx! {
sub_right_in.append(val)
}
}
print(pre);
print(vin);
//递归调用下
root.left = reConstruct(pre: sub_left_pre , vin: sub_left_in)
root.right = reConstruct(pre: sub_right_pre, vin: sub_right_in)
return root;
}
var a = [1,2,4,7,3,5,6,8]
var b = [4,7,2,1,5,3,8,6]
func pre_print(root:TreeNode?) -> Void {
if root == nil {
return;
}else{
print("\(root!.val!) ",terminator:"")
pre_print(root: root!.left);
pre_print(root: root!.right)
}
}
func in_print(root:TreeNode?) -> Void {
if root == nil {
return;
}else{
in_print(root: root!.left)
print("\(root!.val!) ",terminator:"")
in_print(root: root!.right)
}
}
var root = reConstruct(pre: a, vin: b);
pre_print(root: root);
print("\n")
in_print(root: root);
Paste_Image.png
可以看到上面函数执行的递归过程是正确的，并且根据构建出的树的根节点进行前序和中序打印和输入是一样的。
