【华为OD机试】2024年真题C卷（Python）-二叉树计算

题目描述：

给定一个二叉树，请设计一个算法，计算二叉树中任意两个不同节点路径的最大值差。节点路径是从根节点到任何叶节点的节点序列。

输入描述：

第一行包含整数 T(1 <= T <= 100)，表示测试用例的数量。每个测试用例的第一行是一个整数 N(1 <= N <= 100)，表示二叉树的节点数。然后是 N 行，每行包含三个整数 X，L，R（-10000 <= X <= 10000，-1 <= L, R <= N 且 L 和 R 互不相同），表示节点的值和其子节点的索引。如果 L 或 R 是 -1，则表示没有相应的子节点。

输出描述：

对于每个测试用例，输出一个整数，表示任意两个不同节点路径的最大值差。

解法1：

# 二叉树节点定义
class Node:
    def __init__(self, x, left=None, right=None):
        self.val = x
        self.left = left
        self.right = right
 
# 计算二叉树任意两节点路径的最大值差
def maxPathDiff(root):
    def dfs(node):
        if not node:
            return float('-inf'), float('-inf')
        left_max, left_min = dfs(node.left)
        right_max, right_min = dfs(node.right)
        # 计算以当前节点为根的子树的最大路径和
        max_sum = node.val + max(0, max(left_max, left_min) + node.val, max(right_max, right_min) + node.val)
        # 计算以当前节点为根的子树的最小路径和
        min_sum = node.val + min(0, min(left_max, left_min) + node.val, min(right_max, right_min) + node.val)
        # 更新全局最大值差
        global max_diff
        max_diff = max(max_diff, max_sum - min_sum)
        return max_sum, min_sum
 
    max_diff = float('-inf')
    dfs(root)
    return max_diff
 
# 示例用法
# 构建二叉树
root = Node(10, Node(2, Node(3, Node(4), Node(5)), Node(6)), Node(7, Node(8), Node(9)))
# 计算最大值差
print(maxPathDiff(root))  # 输出应为最大值差，例如：1

这段代码首先定义了一个二叉树节点类 Node，然后定义了一个函数 maxPathDiff，该函数接收二叉树的根节点作为参数，并递归遍历二叉树，计算以每个节点为根的子树的最大路径和和最小路径和，并更新全局变量 max_diff 为遇到的最大值差。最后，使用给定的二叉树示例来调用 maxPathDiff 函数并打印结果。