สมมติว่าเรามีต้นไม้ไบนารี เราต้องส่งคืนการสั่งซื้อล่วงหน้าของต้นไม้นั้น ดังนั้นถ้าต้นไม้เป็นเหมือน −
จากนั้นการสั่งจองล่วงหน้าจะเป็น:[3,9,20,15,7]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- สร้างรายการว่างที่เรียกว่า res and st.
- โหนด :=รูท
- ในขณะที่โหนดหรือ st ไม่ว่างเปล่า
- ในขณะที่โหนดไม่เป็นโมฆะ
- แทรก val ของ node ลงใน res แทรก node ลงใน st และตั้งค่า node :=ด้านซ้ายของ node
- temp :=องค์ประกอบสุดท้ายของ st และลบองค์ประกอบสุดท้ายของ st
- ถ้า right of temp แล้ว
- โหนด :=ด้านขวาของอุณหภูมิ
- ในขณะที่โหนดไม่เป็นโมฆะ
- ผลตอบแทน
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
class TreeNode: def __init__(self, data, left = None, right = None): self.data = data self.left = left self.right = right def insert(temp,data): que = [] que.append(temp) while (len(que)): temp = que[0] que.pop(0) if (not temp.left): temp.left = TreeNode(data) break else: que.append(temp.left) if (not temp.right): temp.right = TreeNode(data) break else: que.append(temp.right) def make_tree(elements): Tree = TreeNode(elements[0]) for element in elements[1:]: insert(Tree, element) return Tree class Solution(object): def preorderTraversal(self, root): res = [] st = [] node = root while node or st: while node: if node.data != None: res.append(node.data) st.append(node) node = node.left temp = st[-1] st.pop() if temp.right: node = temp.right return res ob1 = Solution() head = make_tree([3,9,20,None,None,15,7]) print(ob1.preorderTraversal(head))
อินพุต
[3,9,20,null,null,15,7]
ผลลัพธ์
[3, 9, 20, 15, 7]
