สมมติว่าเรามีการข้ามผ่านคำสั่งภายหลังหนึ่งรายการของแผนผังการค้นหาแบบไบนารี เราต้องหาแผนผังการค้นหาแบบไบนารีจากมัน
ดังนั้น หากอินพุตเป็น [6, 12, 10, 55, 45, 15] ผลลัพธ์ก็จะออกมา
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดฟังก์ชัน Solve() การดำเนินการนี้จะเป็นการสั่งทางไปรษณีย์
-
n :=ขนาดของการสั่งซื้อทางไปรษณีย์
-
root :=สร้างโหนดต้นไม้ใหม่ด้วยองค์ประกอบสุดท้ายของ postorder
-
stk :=สแต็ค
-
แทรกรูทลงใน stk
-
ฉัน :=n - 2
-
ในขณะที่ i>=0, ทำ
-
x :=สร้างโหนดใหม่ด้วยค่า postorder[i]
-
ในขณะที่ stk ไม่ว่างเปล่าและ postorder[i] <ค่าสูงสุดของ stk ให้ทำ
-
temp :=ด้านบนของ stk
-
ลบองค์ประกอบด้านบนออกจาก stk
-
-
ถ้า temp ไม่เป็นโมฆะ
-
temp.left :=x
-
-
มิฉะนั้น
-
ด้านขวาขององค์ประกอบบนสุด stk :=x
-
-
ใส่ x ลงใน stk
-
ผม :=ผม - 1
-
-
คืนค่ารูท
-
จากวิธีหลักให้ทำดังต่อไปนี้ -
-
ส่งคืนการแก้ (การสั่งซื้อทางไปรษณีย์)
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
class TreeNode: def __init__(self, data = 0): self.val = data self.left = None self.right = None def solve(postorder): n = len(postorder) root = TreeNode(postorder[n - 1]) stk = [] stk.append(root) i = n - 2 while ( i >= 0): x = TreeNode(postorder[i]) temp = None while (len(stk) > 0 and postorder[i] < stk[-1].val) : temp = stk[-1] stk.pop() if (temp != None): temp.left = x else: stk[-1].right = x stk.append(x) i = i - 1 return root def build_tree(postorder): return solve(postorder) def inord( node): if node: inord(node.left) print( node.val, end = " ") inord(node.right) postorder = [6, 12, 10, 55, 45, 15] root = build_tree(postorder) print( "Inorder traversal:", end = " ") inord(root)
อินพุต
[6, 12, 10, 55, 45, 15]
ผลลัพธ์
6 10 12 15 45 55
