สมมติว่าเรามีลำดับการข้ามผ่านของ inorder และ preorder ของไบนารีทรี เราต้องสร้างต้นไม้จากลำดับเหล่านี้ ดังนั้นหากลำดับล่วงหน้าและลำดับที่ไม่เรียงลำดับคือ [3,9,20,15,7] และ [9,3,15,20,7] ต้นไม้นั้นจะเป็น −
ให้เราดูขั้นตอน -
- สมมติว่าเมธอดนี้เรียกว่า buildTree โดยมีรายการสั่งซื้อล่วงหน้าและรายการเรียงลำดับ
- root :=โหนดแรกจากการสั่งซื้อล่วงหน้า และลบโหนดแรกออกจากการสั่งซื้อล่วงหน้า
- root_index :=ดัชนีของ root.val จากรายการ inorder
- left or root :=buildTree(preorder, subset of inorder from 0 to root_index)
- right or root :=buildTree(preorder, subset of inorder from root_index + 1 to end)
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
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([3,9,20,15,7], [9,3,15,20,7]))
อินพุต
[3,9,20,15,7] [9,3,15,20,7]
ผลลัพธ์
9, 3, 15, 20, 7,
