首页蓝桥杯树上选点python

蓝桥杯树上选点python

时间: 2024-04-09 14:26:45 浏览: 182

蓝桥杯是中国最大的IT技能竞赛之一，树上选点是其中的一道题目。这道题目要求在给定的树上选择一个点，使得该点到其他所有点的距离之和最小。解决这个问题可以使用动态规划的思想。首先，我们可以从叶子节点开始，计算每个节点到其子节点的距离之和。然后，将子节点的距离之和加上当前节点到子节点的距离，得到当前节点到其他所有点的距离之和。最后，选择距离之和最小的节点作为结果。以下是一个用Python实现的示例代码： ```python class TreeNode: def __init__(self, val): self.val = val self.children = [] def dfs(node): if not node.children: return 0 total_distance = 0 for child in node.children: child_distance = dfs(child) total_distance += child_distance + child.val return total_distance def findOptimalNode(root): min_distance = float('inf') optimal_node = None for child in root.children: distance = dfs(child) + child.val if distance < min_distance: min_distance = distance optimal_node = child return optimal_node # 构建树 root = TreeNode(0) node1 = TreeNode(1) node2 = TreeNode(2) node3 = TreeNode(3) node4 = TreeNode(4) root.children = [node1, node2] node1.children = [node3, node4] # 寻找最优节点 optimal_node = findOptimalNode(root) print("最优节点的值为:", optimal_node.val) ```

阅读全文