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