สมมติว่าเรามีไบนารีทรี เราต้องแสดงค่าของแต่ละระดับโดยสลับจากซ้ายไปขวาและขวาไปซ้าย
ดังนั้นหากอินพุตเป็นแบบ
จากนั้นผลลัพธ์จะเป็น [5, -10, 4, -2, -7, 15]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
ถ้ารูทเป็นโมฆะ
-
กลับรายการใหม่
-
-
s1 :=รายการเริ่มแทรกรูท
-
s2 :=รายการใหม่
-
res :=รายการใหม่
-
ขณะที่ s1 ไม่ว่าง หรือ s2 ไม่ว่าง ให้ทำ
-
ขณะที่ s1 ไม่ว่างให้ทำ
-
node :=ลบองค์ประกอบสุดท้ายออกจาก s1
-
หากโหนดที่เหลือไม่เป็นโมฆะ
-
แทรกด้านซ้ายของโหนดที่ส่วนท้ายของ s2
-
-
หากสิทธิ์ของโหนดไม่เป็นโมฆะ
-
แทรกด้านขวาของโหนดที่ส่วนท้ายของ s2
-
-
แทรกค่าของโหนดที่ส่วนท้ายของความละเอียด
-
-
ในขณะที่ s2 ไม่ว่างให้ทำ
-
node :=ลบองค์ประกอบสุดท้ายออกจาก s2
-
หากสิทธิ์ของโหนดไม่เป็นโมฆะ
-
แทรกด้านขวาของโหนดที่ส่วนท้ายของ s1
-
-
ถ้าด้านซ้ายของโหนดไม่ว่างแล้ว
-
แทรกด้านซ้ายของโหนดที่ส่วนท้ายของ s1
-
-
แทรกค่าของโหนดที่ส่วนท้ายของความละเอียด
-
-
-
ผลตอบแทน
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
class TreeNode: def __init__(self, data, left = None, right = None): self.val = data self.left = left self.right = right class Solution: def solve(self, root): if not root: return [] s1 = [root] s2 = [] res = [] while s1 or s2: while s1: node = s1.pop() if node.left: s2.append(node.left) if node.right: s2.append(node.right) res.append(node.val) while s2: node = s2.pop() if node.right: s1.append(node.right) if node.left: s1.append(node.left) res.append(node.val) return res ob = Solution() root = TreeNode(5) root.left = TreeNode(4) root.right = TreeNode(-10) root.left.left = TreeNode(-2) root.right.left = TreeNode(-7) root.right.right = TreeNode(15) print(ob.solve(root))
อินพุต
root = TreeNode(5) root.left = TreeNode(4) root.right = TreeNode(-10) root.left.left = TreeNode(-2) root.right.left = TreeNode(-7) root.right.right = TreeNode(15)
ผลลัพธ์
[5, -10, 4, -2, -7, 15]
