用 Python 编写程序来查找节点和后代之间的差异

pythonserver side programmingprogramming

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

因此，如果输入如下

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

为了解决这个问题，我们将遵循以下步骤 −

定义一个函数 dfs() 。这将获取节点
如果节点不为空，则
- 返回具有正无穷和负无穷的列表
left := dfs(节点左侧)
right := dfs(节点右侧)
res := 一对(left[0]、right[0] 和节点值的最小值，left[1]、right[1] 和节点值的最大值)
ans := ans、(节点值 - res[0])和(res[1] - 节点值)的最大值
返回 res
从 main 方法，执行以下操作 −
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)