मान लीजिए हमारे पास एक बाइनरी ट्री है, हमें प्रत्येक लेवल के मानों को बारी-बारी से बाएं-से-दाएं और दाएं-से-बाएं दिखाना है।
उदाहरण के लिए, यदि इनपुट निम्न ट्री है:
तो आउटपुट [5, -10, 4, -2, -7, 15] होगा।
इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:
यदि
rootnull है, तो खाली सूची लौटाएं।s1 := [root]औरs2 := []दो स्टैक बनाएं।res := []परिणाम सूची।जब तक
s1याs2खाली नहीं हैं:जब तक
s1खाली नहीं है:node := s1.pop()।यदि
node.leftहै, तोs2.append(node.left)।यदि
node.rightहै, तोs2.append(node.right)।res.append(node.val)।
जब तक
s2खाली नहीं है:node := s2.pop()।यदि
node.rightहै, तोs1.append(node.right)।यदि
node.leftहै, तोs1.append(node.left)।res.append(node.val)।
resलौटाएं।
उदाहरण
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]
