数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究Python程序：查找节点与其后代之间的差值
假设我们有一棵二叉树，我们需要找到任何节点与其后代之间最大的绝对差值。
因此，如果输入类似于
那么输出将是 7，因为最大的绝对差值是在节点 8 和 1 之间。
为了解决这个问题，我们将遵循以下步骤：
- 定义一个函数 dfs()。这将接收节点作为参数。
- 如果节点不为空，则
- 返回一个包含正无穷大和负无穷大的列表。
- left := dfs(节点的左子节点)
- right := dfs(节点的右子节点)
- res := 一对值 (left[0]、right[0] 和节点值的最小值，以及 left[1]、right[1] 和节点值的最大值)
- ans := ans、(节点值 - res[0]) 和 (res[1] - 节点值) 中的最大值
- 返回 res
- 从主方法中执行以下操作：
- ans := 0
- dfs(根节点)
- 返回 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
更新于: 2020年11月19日
103 次浏览
广告