สมมุติว่าเรามีไบนารีทรี เราต้องสำรวจต้นไม้นี้โดยใช้รูปแบบการข้ามผ่านแบบ inorder โดยไม่ใช้การเรียกซ้ำ ดังนั้นถ้าต้นไม้เป็นเหมือน
จากนั้นให้ข้ามไปเป็น [2,5,7,10,15,20]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- สร้างอาร์เรย์และสแต็กสองอาร์เรย์ ตั้งค่า curr :=root
- เรียกใช้หนึ่งวนไม่สิ้นสุด
- ในขณะที่กระแสไม่เป็นโมฆะ
- ดัน curr ไปที่ stack และตั้งค่า curr :=left of curr
- เมื่อความยาวของ stack =0 แล้วคืนค่า res
- node :=แตกองค์ประกอบจากสแต็ก
- ใส่ค่าของโหนดลงใน res
- curr :=ด้านขวาของสกุลเงิน
- ในขณะที่กระแสไม่เป็นโมฆะ
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
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 inorderTraversal(self, root): res, stack = [], [] current = root while True: while current: stack.append(current) current = current.left if len(stack) == 0: return res node = stack[-1] stack.pop(len(stack)-1) if node.data != None: res.append(node.data) current = node.right return res ob1 = Solution() root = make_tree([10,5,15,2,7,None,20]) print(ob1.inorderTraversal(root))
อินพุต
[10,5,15,2,7,null,20]
ผลลัพธ์
[2,5,7,10,15,20]
