สมมติว่าเรามีลำดับการข้ามผ่าน inorder และ postorder ของไบนารีทรี เราต้องสร้างต้นไม้จากลำดับเหล่านี้ ดังนั้นหากลำดับหลังและลำดับที่ไม่เป็นระเบียบคือ [9,15,7,20,3] และ [9,3,15,20,7] ต้นไม้นั้นจะเป็น −
มาดูขั้นตอนกันเลย -
- สมมติว่าเมธอดนี้เรียกว่า buildTree โดยมีรายการสั่งซื้อล่วงหน้าและรายการเรียงลำดับ
- root :=โหนดสุดท้ายจาก postorder และลบโหนดแรกออกจาก postorder
- root_index :=ดัชนีของ root.val จากรายการ inorder
- left or root :=buildTree(ส่วนย่อยของ inorder จาก root_index + 1 ถึง end, postorder)
- ถูกต้องหรือรูท :=buildTree(ชุดย่อยของ inorder จากดัชนี 0 ถึง root_index, postorder)
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
class TreeNode: def __init__(self, data, left = None, right = None): self.data = data self.left = left self.right = right def print_tree(root): #print using inorder traversal if root is not None: print_tree(root.left) print(root.data, end = ', ') print_tree(root.right) class Solution(object): def buildTree(self, preorder, inorder): if inorder: root = TreeNode(preorder.pop(0)) root_index = inorder.index(root.data) root.left = self.buildTree(preorder,inorder[:root_index]) root.right = self.buildTree(preorder,inorder[root_index+1:]) return root ob1 = Solution() print_tree(ob1.buildTree([9,3,15,20,7], [9,15,7,20,3]))
อินพุต
[9,3,15,20,7] [9,15,7,20,3]
ผลลัพธ์
9, 15, 7, 20, 3,
