輸入某二叉樹的前序遍歷和中序遍歷的結果，請重建出該二叉樹痛阻。假設輸入的前序遍歷和中序遍歷的結果中都不含重復的數(shù)字菌瘪。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}，則重建二叉樹并返回阱当。
第一次看到這個題目感覺：這種題還能編程寫出來俏扩，這不是某些面試的題目嗎，根據(jù)指定的二叉樹遍歷順序（前中弊添，后中）確定二叉樹的結構录淡。讓自己在紙上自己看看還行，編程怎么寫呢油坝，在紙上畫了畫嫉戚，首先沒有想到遞歸的方式，本想通過兩個for循環(huán)澈圈，外面的循環(huán)是前序數(shù)組彬檀，里面的是中序，前序確定根節(jié)點比較容易瞬女，比如1是樹的根節(jié)點窍帝，那2是根的左子樹還是右子樹呢，僅僅根據(jù)前序是無法判斷的诽偷，這時候要根據(jù)中序坤学，2在1的左邊，所以2是1的左子樹根節(jié)點报慕，但是始終沒有考慮好一個完整的步驟深浮。后來開始想到了遞歸，因為樹就是一個遞歸結構卖子。
首先可以判定1是根節(jié)點所以可以將上述的兩個序列分成4部分：
前序:[2,4,7]和[3,5,6,8]
中序: [4,7,2]和[5,3,8,6]
然后右 [2,4,7]和[4,7,2]構建新的樹作為根節(jié)點的左子樹略号，因為這些點在中序中位于1的左邊刑峡。同理[3,5,6,8]和[5,3,8,6]構建根節(jié)點的右子樹洋闽。
可以很容易看到除了數(shù)組范圍變小了，其他的求解過程依舊沒有變突梦，前序的第一個元素的依然是構建的樹的根節(jié)點诫舅。其他分割策略完全相同。
為了方便本地測試宫患，代碼使用了swift(題目在線測評網(wǎng)站上沒有提供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
}
//根節(jié)點在中序的位置
let r_idx = vin.index(of: pre[0]);
//前序的第一個就是樹的根節(jié)點
let root = TreeNode(val: pre[0]);
var sub_left_pre = [Int]()
var sub_right_pre = [Int]()
for val in pre {
//前序中位于根節(jié)點之前的中序的值，作為根節(jié)點的左子樹的前序序列虚汛，否則作為右子樹的前序序列
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() {
//中序里面匾浪，根節(jié)點之前的元素序列作為左子樹的中序序列，之后的作為右子樹序列
if i < r_idx! {
sub_left_in.append(val)
}
else if i > r_idx! {
sub_right_in.append(val)
}
}
print(pre);
print(vin);
//遞歸調(diào)用下
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);
可以看到上面函數(shù)執(zhí)行的遞歸過程是正確的卷哩，并且根據(jù)構建出的樹的根節(jié)點進行前序和中序打印和輸入是一樣的蛋辈。
