在Python中查找节点和后代之间的差异的程序

在Python中查找节点和后代之间的差异的程序

假设我们有一棵二叉树,我们必须找到任何节点和其后代之间的最大绝对差异。

因此,如果输入如下所示:

在Python中查找节点和后代之间的差异的程序

那么输出将是7,因为最大绝对差异在节点8和1之间。

为了解决这个问题,我们将按照以下步骤进行 –

  • 定义一个函数dfs()。这将取node作为参数。
  • 如果node不为null,则返回一个包含正无穷和负无穷的列表。
      • left:= dfs(左节点)
  • right:= dfs(右节点)
  • res:=一对 (left[0]、right[0]和node的值的最小值,left[1]、right [1]和node的值的最大值)。
  • ans:=ans、(node的值-res [0])和(res [1]-node的值)的最大值。
  • 返回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)
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)

输出

7

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程