สมมติว่าเราต้องสร้างแผนผังการค้นหาแบบไบนารีที่ตรงกับการข้ามผ่านของการสั่งซื้อล่วงหน้าที่กำหนด ดังนั้นหากการสั่งจองล่วงหน้าเป็นเหมือน [8,5,1,7,10,12] ผลลัพธ์จะเป็น [8,5,10,1,7,null,12] ดังนั้นต้นไม้จะเป็น:
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- root :=0 th โหนดของรายการการสั่งผ่านล่วงหน้า
- stack :=a stack และกด root ลงใน stack
- สำหรับแต่ละองค์ประกอบ i จากองค์ประกอบที่สองของรายการสั่งซื้อล่วงหน้า
- i :=โหนดที่มีค่า i
- ถ้าค่าของ i <ด้านบนขององค์ประกอบบนสแต็กแล้ว
- ด้านซ้ายของโหนดบนสุดของสแต็ก :=i
- แทรก i ลงในสแต็ก
- อย่างอื่น
- ในขณะที่สแต็กไม่ว่างเปล่า และสแต็คค่าองค์ประกอบบนสุด <ค่าของ i
- สุดท้าย :=ด้านบนของสแต็ก
- องค์ประกอบป๊อปจากสแต็ก
- ทางขวาของโหนดสุดท้าย :=i
- แทรก i ลงในสแต็ก
- ในขณะที่สแต็กไม่ว่างเปล่า และสแต็คค่าองค์ประกอบบนสุด <ค่าของ i
- คืนราก
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
class Solution(object): def bstFromPreorder(self, preorder): """ :type preorder: List[int] :rtype: TreeNode """ root = TreeNode(preorder[0]) stack = [root] for i in preorder[1:]: i = TreeNode(i) if i.val<stack[-1].val: stack[-1].left = i stack.append(i) else: while stack and stack[-1].val<i.val: last = stack.pop(-1) last.right = i stack.append(i) return root
อินพุต
[8,5,1,7,10,12]
ผลลัพธ์
[8,5,10,1,7,null,12]
