這是劍指offer的一道題系洛。
輸入某二叉樹(shù)的前序遍歷和中序遍歷的結(jié)果贺拣，請(qǐng)重建出該二叉樹(shù)驻债。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字珍语。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}，則重建出如下圖所示的二叉樹(shù)并輸出它的頭結(jié)點(diǎn)。
思路如下：
- 中序遍歷中根節(jié)點(diǎn)之前的節(jié)點(diǎn)屬于左子樹(shù)切黔，之后為右子樹(shù)砸脊。
- 前序遍歷的第一個(gè)節(jié)點(diǎn)為根節(jié)點(diǎn)。
- 前序遍歷結(jié)果的排列為：根節(jié)點(diǎn)-左子樹(shù)節(jié)點(diǎn)-右子樹(shù)節(jié)點(diǎn)
- 拆分出左子樹(shù)和右子樹(shù)遞歸重復(fù)上述過(guò)程
package main
import (
"fmt"
)
// 重建二叉樹(shù)
type Node struct {
value int64
left *Node
right *Node
}
func main() {
preOrder := []int64{1,2,4,7,3,5,6,8}
inOrder := []int64{4,7,2,1,5,3,8,6}
tree := constructBTree(preOrder, inOrder)
//將構(gòu)建好的二叉樹(shù) 輸出先序遍歷和中序遍歷的結(jié)果 用于檢驗(yàn)
preCatTree(tree)
inCatTree(tree)
}
//重建二叉樹(shù)
func constructBTree(preOrder, inOrder []int64) *Node{
l := len(preOrder)
if l == 0{
return nil
}
root := &Node{
value:preOrder[0],
}
if l == 1{
return root
}
leftLen := 0
rightLen := 0
for _,v := range inOrder{
if v == root.value{
break
}
leftLen++ //根節(jié)點(diǎn)之前的為左子樹(shù)長(zhǎng)度
}
rightLen = l - leftLen - 1 //右子樹(shù)長(zhǎng)度
if leftLen > 0{
//fmt.Println("左子樹(shù)",preOrder[1:leftLen+1], inOrder[0:leftLen]) //可打開(kāi)注釋查看詳細(xì)過(guò)程
root.left = constructBTree(preOrder[1:leftLen+1], inOrder[0:leftLen])
}
if rightLen >0{
//fmt.Println("右子樹(shù)",preOrder[leftLen+1:], inOrder[leftLen+1:])
root.right = constructBTree(preOrder[leftLen+1:], inOrder[leftLen+1:])
}
return root
}
func preCatTree(t *Node) {
fmt.Println(t.value)
if t.left!=nil{
preCatTree(t.left)
}
if t.right!=nil{
preCatTree(t.right)
}
}
func inCatTree(t *Node) {
if t.left!=nil{
inCatTree(t.left)
}
fmt.Println(t.value)
if t.right!=nil{
inCatTree(t.right)
}
}
