पायथन में नोड और उसके वंशज के बीच अंतर खोजने का प्रोग्राम

मान लीजिए हमारे पास एक बाइनरी ट्री है, हमें किसी भी नोड और उसके वंशजों के बीच सबसे बड़ा निरपेक्ष अंतर ढूंढना है।

उदाहरण के लिए, यदि इनपुट ट्री है:

तो आउटपुट 7 होगा क्योंकि सबसे बड़ा निरपेक्ष अंतर नोड्स 8 और 1 के बीच है।

समाधान दृष्टिकोण

इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे (पोस्ट-ऑर्डर DFS):

एक फंक्शन dfs() परिभाषित करें जो node लेता है:
यदि node नल है: [inf, -inf] लौटाएं
left := dfs(node.left), right := dfs(node.right)
res := [min(left[0], right[0], node.val), max(left[1], right[1], node.val)]
ans := max(ans, node.val - res[0], res[1] - node.val)
res लौटाएं
मुख्य मेथड से: ans=0, dfs(root), ans लौटाएं

उदाहरण कोड

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):
        def dfs(node):
            if not node:
                return [float("inf"), float("-inf")]
            left = dfs(node.left)
            right = dfs(node.right)
            res = [min(left[0], right[0], node.val), max(left[1], right[1], node.val)]
            self.ans = max(self.ans, node.val - res[0], res[1] - node.val)
            return res
        self.ans = 0
        dfs(root)
        return self.ans

ob = Solution()
root = TreeNode(1)
root.left = TreeNode(5)
root.right = TreeNode(3)
root.right.left = TreeNode(2)
root.right.right = TreeNode(8)
root.right.left.left = TreeNode(7)
root.right.left.right = TreeNode(4)
print(ob.solve(root))

इनपुट

root = TreeNode(1) ... (पूर्ण ट्री)