兩個節點之間的距離

 要計算二元樹中兩個節點（如葉子節點 1 和 10）之間的距離，可以分為以下幾個步驟：

步驟

1. 找出節點 1 和 10 的最近共同祖先（LCA，Lowest Common Ancestor）:
   • 最近共同祖先是這兩個節點在樹中的最深的共同節點。
2. 計算從最近共同祖先到節點 1 和節點 10 的距離:
   • 距離是沿樹的邊數（Edge Count）。
3. 總距離:
   • 總距離是從 LCA 到節點 1 的距離加上從 LCA 到節點 10 的距離。

---

Python 實現

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def insert_node(root, value):
    if root is None:
        return TreeNode(value)
    if value < root.value:
        root.left = insert_node(root.left, value)
    else:
        root.right = insert_node(root.right, value)
    return root

def build_tree(values):
    root = None
    for value in values:
        root = insert_node(root, value)
    return root

# 找最近共同祖先 (LCA)
def find_lca(node, n1, n2):
    if node is None:
        return None
    # 如果當前節點是 n1 或 n2，直接返回
    if node.value == n1 or node.value == n2:
        return node

    # 在左子樹和右子樹中查找
    left_lca = find_lca(node.left, n1, n2)
    right_lca = find_lca(node.right, n1, n2)

    # 如果兩邊都有值，當前節點就是 LCA
    if left_lca and right_lca:
        return node

    # 否則返回非空的一側
    return left_lca if left_lca is not None else right_lca

# 計算從某節點到目標節點的距離
def find_distance(node, target, distance):
    if node is None:
        return -1
    if node.value == target:
        return distance
    # 搜索左子樹和右子樹
    left_distance = find_distance(node.left, target, distance + 1)
    if left_distance != -1:
        return left_distance
    return find_distance(node.right, target, distance + 1)

# 計算兩個節點的距離
def distance_between_nodes(root, n1, n2):
    lca = find_lca(root, n1, n2)  # 找到最近共同祖先
    if lca is None:
        return -1  # 若無 LCA，返回 -1（不可能發生在此問題中）
    d1 = find_distance(lca, n1, 0)  # LCA 到節點 n1 的距離
    d2 = find_distance(lca, n2, 0)  # LCA 到節點 n2 的距離
    return d1 + d2  # 總距離

# 建立二元樹
values = [6, 3, 5, 7, 9, 10, 8, 1, 4, 2]
tree_root = build_tree(values)

# 計算葉子 1 和 10 的距離
distance = distance_between_nodes(tree_root, 1, 10)

# 輸出結果
print("葉子 1 和 10 的距離:", distance)

---

運行結果

對於這棵二元樹：

          6
       /     \
     3         7
    / \          \
   1   5         9
    \  /        / \
     2 4       8  10

最近共同祖先（LCA）是根節點 6：

• 從節點 6 到 1 的距離是 2（6 -> 3 -> 1）。
• 從節點 6 到 10 的距離是 3（6 -> 7 -> 9 -> 10）。

因此，葉子 1 和 10 的總距離是：

2 + 3 = 5

---

結果

葉子 1 和 10 的距離是 5。