您好,登錄后才能下訂單哦!
今天就跟大家聊聊有關(guān)遍歷構(gòu)造python二叉樹的示例分析,可能很多人都不太了解,為了讓大家更加了解,小編給大家總結(jié)了以下內(nèi)容,希望大家根據(jù)這篇文章可以有所收獲。
根據(jù)一棵樹的前序遍歷與中序遍歷構(gòu)造二叉樹。
注意:
你可以假設(shè)樹中沒有重復(fù)的元素。
例如,給出
前序遍歷 preorder = [3,9,20,15,7]
中序遍歷 inorder = [9,3,15,20,7]
返回如下的二叉樹:
3
/ \
9 20
/ \
15 7
解題思路:
1,前序遍歷的話第一個(gè)一定是根
2,中序遍歷的話和根元素相等的元素左邊一定在左子樹,設(shè)根元素位置為i
3,前序遍歷,前長度為i+1的元素一定在左子樹
4,遞歸求解
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func buildTree(preorder []int, inorder []int) *TreeNode {
if len(preorder) < 1 || len(inorder) < 1 {
return nil
}
if len(preorder) == 1 {
return &TreeNode{
Val: preorder[0],
}
}
if len(inorder) == 1 {
return &TreeNode{
Val: inorder[0],
}
}
i := 0
for ; i < len(inorder); i++ {
if preorder[0] == inorder[i] {
break
}
}
if i == len(inorder) {
return nil
}
h := &TreeNode{
Val: preorder[0],
}
if i == 0 {
h.Right = buildTree(preorder[1:], inorder[i+1:])
} else if i == len(inorder)-1 {
h.Left = buildTree(preorder[1:], inorder[:i])
} else {
h.Left = buildTree(preorder[1:i+1], inorder[:i])
h.Right = buildTree(preorder[i+1:], inorder[i+1:])
}
return h
}
根據(jù)一棵樹的中序遍歷與后序遍歷構(gòu)造二叉樹。
注意:
你可以假設(shè)樹中沒有重復(fù)的元素。
例如,給出
中序遍歷 inorder = [9,3,15,20,7]
后序遍歷 postorder = [9,15,7,20,3]
返回如下的二叉樹:
3
/ \
9 20
/ \
15 7
解題思路:
1,后序遍歷的話最后一個(gè)一定是根
2,中序遍歷的話和根元素相等的元素左邊一定在左子樹,設(shè)根元素位置為i
3,后序遍歷,前長度為i+1的元素一定在左子樹
4,遞歸求解
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */func buildTree(inorder []int, postorder []int) *TreeNode { if len(inorder)<1 ||len(postorder)<1{ return nil } if len(inorder)==1{ return &TreeNode{Val:inorder[0]} } i:=0 for ;i<len(inorder);i++{ if postorder[len(postorder)-1]==inorder[i]{ break } } h:=&TreeNode{Val:postorder[len(postorder)-1]} if i==len(postorder)-1{ h.Left=buildTree(inorder[:i],postorder[:i]) }else if i==0{ h.Right=buildTree(inorder[1:],postorder[:len(postorder)-1]) }else{ h.Left=buildTree(inorder[:i],postorder[:i]) h.Right=buildTree(inorder[i+1:],postorder[i:len(postorder)-1]) } return h}
看完上述內(nèi)容,你們對(duì)遍歷構(gòu)造python二叉樹的示例分析有進(jìn)一步的了解嗎?如果還想了解更多知識(shí)或者相關(guān)內(nèi)容,請關(guān)注億速云行業(yè)資訊頻道,感謝大家的支持。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。