मान लीजिए हमारे पास एक बाइनरी ट्री और moves नामक स्ट्रिंग्स की एक सूची है जिसमें "R" (दाएं), "L" (बाएं) और "U" (ऊपर) शामिल हैं। रूट से शुरू करके, हमें moves में प्रत्येक चाल को निष्पादित करके ट्री को पार करना होगा जहां: "R" दाएं चाइल्ड को पार करने का संकेत देता है। "L" बाएं चाइल्ड को पार करने का संकेत देता है। "U" उसके पैरेंट को पार करने का संकेत देता है।
तो, यदि इनपुट इस तरह है

["R","R","U","L"], तो आउटपुट 3 होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:
- past := एक नई सूची
- moves में प्रत्येक चाल के लिए, करें
- root को past के अंत में डालें
- यदि चाल "L" के समान है, तो root := root का बाएं
- अन्यथा जब चाल "R" के समान है, तो root := root का दाएं
- अन्यथा,
- past से अंतिम तत्व हटाएं
- root := past से अंतिम तत्व और इसे past से हटाएं
- root का मान लौटाएं
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
उदाहरण
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:
past.pop()
root = past.pop()
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))
इनपुट
root = TreeNode(2)
root.right = TreeNode(4)
root.right.left = TreeNode(3)
root.right.right = TreeNode(5)
["R","R","U","L"]
आउटपुट
3