ปัญหา
กำหนด Binary Tree และ list moves = ["R", "L", "U"] เริ่มจาก root:
R = ไป right child, L = ไป left child, U = กลับไป parent
หาค่า node ที่หยุดสุดท้าย
ตัวอย่าง: Tree: 2→right→4→left→3, moves=["R","R","U","L"] → 3
วิธีแก้: เก็บ Path (Stack)
ใช้ list `past` เก็บ node ที่ผ่านมา เพื่อกลับไป parent ได้
อัลกอริทึม
- past = []
- สำหรับแต่ละ move:
- push root ปัจจุบันเข้า past
- L: root = root.left
- R: root = root.right
- U: pop past 2 ครั้ง (pop ปัจจุบัน, pop parent) → root = parent
- คืนค่า root.val
โค้ด Python
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, moves):
past = []
for move in moves:
past.append(root)
if move == "L":
root = root.left
elif move == "R":
root = root.right
else: # "U"
past.pop() # pop current
root = past.pop() # pop parent, set as current
return root.val
# ทดสอบ
ob = Solution()
root = TreeNode(2)
root.right = TreeNode(4)
root.right.left = TreeNode(3)
root.right.right = TreeNode(5)
traverse = ["R", "R", "U", "L"]
print(ob.solve(root, traverse)) # 3
# Trace:
# Start: 2, past=[]
# R: past=[2], root=4
# R: past=[2,4], root=3
# U: past=[2,4,3], pop→3, pop→4, root=4
# L: past=[2,4], root=3
# Result: 3
ความซับซ้อน
- Time: O(m) - m = จำนวน moves
- Space: O(m) - stack past
สมมติฐาน
- Moves เสมอ valid (ไม่เดินนอก tree)
- Tree มี parent pointer ไม่ได้ → ต้องเก็บ path เอง
ประยุกต์: Tree Navigation
ใช้ใน file system traversal, DOM navigation, game tree search
