パスの合計と最近共通祖先
再帰的な下降処理を使い、一般的な二分木でroot-to-leaf path sum、all-paths-sum、lowest-common-ancestorを解きます。
「パスの合計と最近共通祖先」はCoddyKit上の無料DSA Interview Prepレッスンです。 これはレッスン4/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはDSA Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 DSA Interview Prepコースには全4レッスンが含まれています。
根から葉へのパス合計
パス合計の問題では、根から葉までのパスの合計が目標値になるものが存在するかを判定します。再帰の中で各ノードの値を引きながら、残りの目標値を渡していきます。葉では、残りの値がその葉の値と等しいかを確認します。これにより明示的なパスのリストを保持する必要がなくなり、空間効率が高く、すっきりした実装になります。エッジケースとして、空の木にはパスがないため、すぐにFalseを返します。
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def has_path_sum(root, target):
if not root:
return False
if not root.left and not root.right: # leaf
return root.val == target
remain = target - root.val
return (has_path_sum(root.left, remain) or
has_path_sum(root.right, remain))
root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(8)
root.left.left = TreeNode(11)
root.left.left.left = TreeNode(7)
root.left.left.right = TreeNode(2)
print(has_path_sum(root, 22)) # True: 5->4->11->2すべての根から葉へのパス
すべてのパスを列挙するには、現在のパスをリストとして保持します。各再帰呼び出しで現在のノードの値を追加し、子へ再帰してから、戻るときにpopします（バックトラッキング）。葉に到達したら、現在のパスのスナップショット（list(path)）を記録します。この「選択、再帰、選択解除」というパターンは、木に対するバックトラッキングの基礎です。
def all_path_sums(root, target):
results = []
def dfs(node, path, remaining):
if not node:
return
path.append(node.val)
if not node.left and not node.right and remaining == node.val:
results.append(list(path)) # snapshot
else:
dfs(node.left, path, remaining - node.val)
dfs(node.right, path, remaining - node.val)
path.pop() # backtrack
dfs(root, [], target)
return results
root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(8)
root.left.left = TreeNode(11)
root.left.left.right = TreeNode(2)
root.right.right = TreeNode(5)
print(all_path_sums(root, 22)) # [[5,4,11,2]]パス合計III：任意のパス、任意のノード
パス合計III（LeetCode #437）では、パスの開始点と終了点をどこにしてもよい（根から葉へのパスに限らない）場合に、合計が目標値になるパスの数を数えます。単純な総当たり法の計算量はO(n²)で、各ノードからDFSを実行します。最適なO(n)の方法では累積和のハッシュマップを使い、累積和を追跡しながら、current_sum - targetがそれ以前に何回現れたかを数えます。これは部分配列の合計を求める方法と同じ考え方です。
def path_sum_iii(root, target):
prefix_counts = {0: 1}
def dfs(node, running_sum):
if not node:
return 0
running_sum += node.val
count = prefix_counts.get(running_sum - target, 0)
prefix_counts[running_sum] = prefix_counts.get(running_sum, 0) + 1
count += dfs(node.left, running_sum)
count += dfs(node.right, running_sum)
prefix_counts[running_sum] -= 1 # backtrack
return count
return dfs(root, 0)
root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(-3)
root.left.left = TreeNode(3)
root.left.right = TreeNode(2)
root.right.right = TreeNode(11)
root.left.left.left = TreeNode(3)
root.left.left.right = TreeNode(-2)
root.left.right.right = TreeNode(1)
print(path_sum_iii(root, 8)) # 3最低共通祖先とは
二分木における2つのノードpとqの最低共通祖先（LCA）とは、pとqの両方を子孫に持つ最も深いノードです（ノード自身をそのノードの子孫とみなすこともできます）。LCAは、「2つのノード間の距離」、「2つのノード間のパス」、「BSTの範囲クエリ」などの問題で登場します。LCAの理解は、中級レベルの木の問題に取り組むうえで不可欠です。
# 3
# / \
# 5 1
# / \ / \
# 6 2 0 8
# / \
# 7 4
# LCA(5, 1) = 3 (root)
# LCA(5, 4) = 5 (p itself is ancestor of q)
# LCA(6, 4) = 5
# LCA(7, 4) = 2
# Key insight: the LCA is the node where p and q
# first 'split' into different subtrees.
print('LCA: deepest node that is ancestor of both p and q')LCAの再帰アルゴリズム
洗練された再帰によるLCA解法では、pまたはq自身であるか、部分木にその両方を持つ最初のノードを返します。現在のノードがpまたはqなら、そのノードを返します。それ以外の場合は、左と右に対して再帰します。両方の側がnull以外を返した場合、現在のノードがLCAです。一方の側だけがnull以外の場合は、その結果を上へ伝播します。計算量は時間O(n)、空間O(h)です。
def lowest_common_ancestor(root, p, q):
# Base case: empty or found one of the targets
if not root or root == p or root == q:
return root
# Search both subtrees
left = lowest_common_ancestor(root.left, p, q)
right = lowest_common_ancestor(root.right, p, q)
# If both sides found something, this node is the LCA
if left and right:
return root
# Otherwise, return whichever side found something
return left if left else right
root = TreeNode(3)
root.left = TreeNode(5)
root.right = TreeNode(1)
root.left.left = TreeNode(6)
root.left.right = TreeNode(2)
p, q = root.left, root.right # 5 and 1
lca = lowest_common_ancestor(root, p, q)
print(lca.val) # 3ノード自身が祖先になれる場合のLCA
重要なエッジケースがあります。pがqの祖先である場合（またはその逆）、LCAはp自身です。再帰アルゴリズムはこれを自動的に処理します。pに到達すると、pの部分木を調べることなく、すぐにpを返します。親は、一方の側からpが返され、もう一方の側からnullが返されたことを確認するため、LCAとしてpを上へ伝播します。LCAを実装するときは、必ずこのケースをテストで確認してください。
# Test case: p is ancestor of q
# Tree: 3 -> left=5 -> left=6
# LCA(5, 6) should be 5
root = TreeNode(3)
root.left = TreeNode(5)
root.left.left = TreeNode(6)
p = root.left # node 5
q = root.left.left # node 6
lca = lowest_common_ancestor(root, p, q)
print(lca.val) # 5 (p itself is the LCA)親ポインタを持つ場合のLCA
各ノードが親ポインタを持っている場合、LCAは「2つの連結リストの交差」の問題に置き換えられます。pの祖先を集合に格納し、その後qから上へたどって、その集合に含まれるノードを見つけます。このO(h)時間、O(h)空間の方法は、ノード構造を自分で管理でき、親への参照を保存できるシステム設計面接でよく使われます。
class NodeWithParent:
def __init__(self, val, parent=None):
self.val = val
self.parent = parent
self.left = None
self.right = None
def lca_with_parent(p, q):
ancestors = set()
# Collect all ancestors of p
node = p
while node:
ancestors.add(node)
node = node.parent
# Walk up from q until we hit a known ancestor
node = q
while node:
if node in ancestors:
return node
node = node.parent
return None
print('With parent pointers: O(h) time and space')二分探索木におけるLCA
BSTでは、順序付けの性質によって各ノードがどの部分木にあるかが分かるため、LCAはより簡単に求められます。pとqの両方が現在のノードより小さい場合、LCAは左部分木にあります。両方が大きい場合は、右部分木にあります。それ以外の場合は、現在のノードが両者を分けるため、それがLCAです。これにより、平衡したBSTでは問題をO(log n)に削減できます。
def lca_bst(root, p, q):
if not root:
return None
if p.val < root.val and q.val < root.val:
return lca_bst(root.left, p, q) # both in left
if p.val > root.val and q.val > root.val:
return lca_bst(root.right, p, q) # both in right
return root # split point = LCA
# Iterative BST LCA (no recursion overhead):
def lca_bst_iter(root, p, q):
while root:
if p.val < root.val and q.val < root.val:
root = root.left
elif p.val > root.val and q.val > root.val:
root = root.right
else:
return root
return None
print('BST LCA: O(log n) for balanced trees')2つのノード間の距離
木における2つのノード間の距離は、それらを結ぶパス上の辺の数です。これはLCAから直接計算できます：distance(p, q) = depth(p) + depth(q) - 2 * depth(LCA(p,q))。まずLCAを求め、次に各ノードの深さを数えます。適切なヘルパー関数を使えば、計算量は時間O(n)、空間O(h)です。
def find_depth(root, target, depth=0):
if not root:
return -1
if root == target:
return depth
left = find_depth(root.left, target, depth + 1)
if left != -1:
return left
return find_depth(root.right, target, depth + 1)
def node_distance(root, p, q):
lca = lowest_common_ancestor(root, p, q)
# depth from LCA to p and q
dp = find_depth(lca, p)
dq = find_depth(lca, q)
return dp + dq
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(node_distance(root, root.left.left, root.left.right)) # 2根から葉への最大合計パス
根から葉への最大合計パスでは、根から現在のノードまでの累積合計を追跡します。葉に到達したら、グローバルな最大値と比較します。これは現在のパスの合計をパラメータとして渡す、プレオーダーDFSです。一般的な最大パス合計とは異なり、この方法では根から葉へのパスに限定されるため、より単純です。任意のノード間のパスを考慮する必要はありません。
def max_root_to_leaf_sum(root):
if not root:
return float('-inf')
best = [float('-inf')]
def dfs(node, running):
running += node.val
if not node.left and not node.right: # leaf
best[0] = max(best[0], running)
return
if node.left:
dfs(node.left, running)
if node.right:
dfs(node.right, running)
dfs(root, 0)
return best[0]
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(max_root_to_leaf_sum(root)) # 1+2+5 = 8根から葉までの数値の合計
根から葉までの数値の合計（LeetCode #129）では、根から葉までの各パスを10進数として扱い（たとえば、パス1→2→3は数値123を表します）、それらの合計を求めます。current_number * 10 + node.valを再帰に渡して数値を作ります。各葉で、完成した数値を合計に加えます。これは、蓄積した状態を下方向へ渡すプレオーダーDFSの分かりやすい例です。
def sum_numbers(root):
def dfs(node, num):
if not node:
return 0
num = num * 10 + node.val
if not node.left and not node.right: # leaf
return num
return dfs(node.left, num) + dfs(node.right, num)
return dfs(root, 0)
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
print(sum_numbers(root)) # 12 + 13 = 25
root2 = TreeNode(4)
root2.left = TreeNode(9)
root2.right = TreeNode(0)
root2.left.left = TreeNode(5)
root2.left.right = TreeNode(1)
print(sum_numbers(root2)) # 495 + 491 + 40 = 1026確認テスト
このレッスンで扱ったData Structures & Algorithms — Coding Interview Prepの概念について、理解度を確認しましょう。
レッスンのまとめ
このレッスンでは、パス合計のバリエーション（根から葉へのパス、すべてのパス、累積和を使うパス合計III）、洗練された再帰的な分割による最低共通祖先、順序付けの性質を利用してO(log n)で求めるBSTのLCAを学びました。次は、挿入と検索の操作から二分探索木を始めます。
よくある質問
「パスの合計と最近共通祖先」レッスンは無料ですか？
はい。「パスの合計と最近共通祖先」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、DSA Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 DSA Interview Prepコースには全4レッスンが含まれています。
「パスの合計と最近共通祖先」で何を学びますか？
再帰的な下降処理を使い、一般的な二分木でroot-to-leaf path sum、all-paths-sum、lowest-common-ancestorを解きます。 ブラウザで直接実行するハンズオンコードでDSA Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
DSA Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのDSA Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン4/4です。
「パスの合計と最近共通祖先」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このDSA Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのDSA Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。