मान लीजिए हमारे पास एक बाइनरी ट्री है; हमें एक सूची ढूंढनी है जिसमें रूट का इनऑर्डर ट्रैवर्सल हो। जैसा कि हम जानते हैं, इनऑर्डर ट्रैवर्सल ट्री में सभी नोड्स को ट्रैवर्स करने का एक तरीका है जहां हम:
- बाएं सबट्री को रिकर्सिवली ट्रैवर्स करते हैं।
- वर्तमान नोड को ट्रैवर्स करते हैं।
- दाएं सबट्री को रिकर्सिवली ट्रैवर्स करते हैं।
हमें इस समस्या को इटरेटिव तरीके से हल करने का प्रयास करना है।
उदाहरण के लिए, यदि इनपुट निम्न ट्री है:
तो आउटपुट [12, 13, 4, 16, 7, 14, 22] होगा।
इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे (स्टैक का उपयोग करके इटरेटिव इनऑर्डर):
inorder := [],stack := []।अनंत लूप में निम्न करें:
यदि
rootnull नहीं है:stack.append(root);root = root.left।
अन्यथा यदि
stackखाली नहीं है:root = stack.pop()।inorder.append(root.val)।root = root.right।
अन्यथा, लूप से बाहर निकलें।
inorderलौटाएं।
उदाहरण
class TreeNode: def __init__(self, value): self.val = value self.left = None self.right = None class Solution: def solve(self, root): inorder = [] stack = [] while True: if root: stack.append(root) root = root.left elif stack: root = stack.pop() inorder.append(root.val) root = root.right else: break return inorder ob = Solution() root = TreeNode(13) root.left = TreeNode(12) root.right = TreeNode(14) root.right.left = TreeNode(16) root.right.right = TreeNode(22) root.right.left.left = TreeNode(4) root.right.left.right = TreeNode(7) print(ob.solve(root))
इनपुट
root = TreeNode(13) root.left = TreeNode(12) root.right = TreeNode(14) root.right.left = TreeNode(16) root.right.right = TreeNode(22) root.right.left.left = TreeNode(4) root.right.left.right = TreeNode(7)
आउटपुट
[12, 13, 4, 16, 7, 14, 22]
