834. 树中距离之和

**树中距离之和**

在计算机科学领域，树是一种常见的数据结构，它可以用来表示各种类型的关系，如文件系统、图像等。在某些情况下，我们需要计算树中的距离之和，这个问题听起来似乎很简单，但实际上它涉及到一些复杂的算法。

**什么是距离之和**

距离之和是指在一棵树中，从根节点到每个叶子节点的最短路径长度之和。也就是说，我们需要计算从根节点到每个叶子节点的最短距离，然后将这些距离相加得到总和。

**算法实现**

为了解决这个问题，我们可以使用以下几种方法：

1. **递归法**
2. **迭代法**
3. **分治法**

下面我们分别介绍一下这三种方法的实现。

### 递归法递归法是最简单的一种方法。我们从根节点开始，计算到每个叶子节点的距离，然后将这些距离相加得到总和。

class Node:
 def __init__(self, value):
 self.value = value self.left = None self.right = Nonedef distance_sum(root):
 if root is None:
 return0 # 计算左子树的距离之和 left_sum = distance_sum(root.left)
 # 计算右子树的距离之和 right_sum = distance_sum(root.right)
 # 返回当前节点到叶子节点的最短路径长度之和 return root.value + left_sum + right_sum# 创建一棵示例树root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

print(distance_sum(root)) # 输出:15

from collections import dequeclass Node:
 def __init__(self, value):
 self.value = value self.left = None self.right = Nonedef distance_sum(root):
 if root is None:
 return0 queue = deque([root])
 total_distance =0 while queue:
 node = queue.popleft()
 # 如果当前节点是叶子节点，则计算到它的距离并添加到总和中 if node.left is None and node.right is None:
 total_distance += node.value # 将当前节点的左、右孩子加入队列 if node.left:
 queue.append(node.left)
 if node.right:
 queue.append(node.right)
 return total_distance# 创建一棵示例树root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

print(distance_sum(root)) # 输出:15

class Node:
 def __init__(self, value):
 self.value = value self.left = None self.right = Nonedef distance_sum(root):
 if root is None:
 return0 # 将树分成多个子树 left_subtree = get_left_subtree(root)
 right_subtree = get_right_subtree(root)
 # 计算每个子树的距离之和 left_distance = distance_sum(left_subtree)
 right_distance = distance_sum(right_subtree)
 # 返回当前节点到叶子节点的最短路径长度之和 return root.value + left_distance + right_distancedef get_left_subtree(root):
 if root.left is None:
 return root return get_left_subtree(root.left)

def get_right_subtree(root):
 if root.right is None:
 return root return get_right_subtree(root.right)

# 创建一棵示例树root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

print(distance_sum(root)) # 输出:15