FAAANGコーディング面接完全攻略：ツリーとグラフの核心パターン
ツリーとグラフの問題はFAANG面接において、配列・文字列に次いで出題頻度が高い分野です。特にGoogleとMetaはグラフとツリーの探索問題を非常に重視します。本記事では面接必須の5つの核心パターンを完全なPythonコードと共に徹底解説します。
1. Binary Tree 核心パターン
DFS（深さ優先探索）
DFSはできる限り深く進んでからバックトラックするツリー探索です。再帰とスタックを使った反復の両方で実装できます。
ツリーノードの定義
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
DFS 3種類の巡回（再帰）
中順（Inorder）: 左 → 現在 → 右（BSTでソート順）
def inorder(root):
if not root:
return []
return inorder(root.left) + [root.val] + inorder(root.right)
前順（Preorder）: 現在 → 左 → 右（ツリーのコピー、直列化）
def preorder(root):
if not root:
return []
return [root.val] + preorder(root.left) + preorder(root.right)
後順（Postorder）: 左 → 右 → 現在（ディレクトリサイズ計算）
def postorder(root):
if not root:
return []
return postorder(root.left) + postorder(root.right) + [root.val]
反復DFS（スタック使用）
def inorderIterative(root):
result = []
stack = []
current = root
while current or stack:
できる限り左に移動
while current:
stack.append(current)
current = current.left
current = stack.pop()
result.append(current.val)
current = current.right
return result
def preorderIterative(root):
if not root:
return []
result = []
stack = [root]
while stack:
node = stack.pop()
result.append(node.val)
右を先にスタックへ（左が先に処理されるよう）
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return result
BFS（幅優先探索）— レベル順巡回
from collections import deque
def levelOrder(root):
if not root:
return []
result = []
queue = deque([root])
while queue:
level_size = len(queue)
current_level = []
for _ in range(level_size):
node = queue.popleft()
current_level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(current_level)
return result
例:
ツリー: 3
/ \
9 20
/ \
15 7
出力: [[3], [9,20], [15,7]]
問題 1: 二分木の最大深度（LeetCode 104）
def maxDepth(root) -> int:
if not root:
return 0
return 1 + max(maxDepth(root.left), maxDepth(root.right))
BFS方式
def maxDepthBFS(root) -> int:
if not root:
return 0
depth = 0
queue = deque([root])
while queue:
depth += 1
for _ in range(len(queue)):
node = queue.popleft()
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return depth
**時間計算量:** O(n) — 全ノードを1回訪問
**空間計算量:** O(h) — hはツリーの高さ（偏ったツリーでは最悪O(n)）
問題 2: 二分木を反転させる（LeetCode 226）
def invertTree(root):
if not root:
return None
左右のサブツリーを交換
root.left, root.right = invertTree(root.right), invertTree(root.left)
return root
反復方式（BFS）
def invertTreeBFS(root):
if not root:
return None
queue = deque([root])
while queue:
node = queue.popleft()
node.left, node.right = node.right, node.left
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return root
**時間計算量:** O(n)
**空間計算量:** O(n)
問題 3: 対称な二分木（LeetCode 101）
ツリーが左右対称かどうかを確認せよ。
def isSymmetric(root) -> bool:
def isMirror(left, right):
if not left and not right:
return True
if not left or not right:
return False
return (left.val == right.val and
isMirror(left.left, right.right) and
isMirror(left.right, right.left))
return isMirror(root.left, root.right)
反復方式
def isSymmetricIterative(root) -> bool:
queue = deque([(root.left, root.right)])
while queue:
left, right = queue.popleft()
if not left and not right:
continue
if not left or not right:
return False
if left.val != right.val:
return False
queue.append((left.left, right.right))
queue.append((left.right, right.left))
return True
問題 4: 経路の和 II（LeetCode 113）
ルートからリーフまでの合計がtargetSumになる全経路を見つけよ。
def pathSum(root, targetSum: int):
result = []
def dfs(node, current_path, remaining):
if not node:
return
current_path.append(node.val)
remaining -= node.val
リーフノードで合計が一致したら経路を追加
if not node.left and not node.right and remaining == 0:
result.append(list(current_path))
else:
dfs(node.left, current_path, remaining)
dfs(node.right, current_path, remaining)
バックトラック
current_path.pop()
dfs(root, [], targetSum)
return result
問題 5: 最小共通祖先（LCA）（LeetCode 236）
2つのノードp、qのLCAを見つけよ。
def lowestCommonAncestor(root, p, q):
if not root or root == p or root == q:
return root
left = lowestCommonAncestor(root.left, p, q)
right = lowestCommonAncestor(root.right, p, q)
両側で見つかった場合、現在ノードがLCA
if left and right:
return root
片側のみで見つかった場合、その側がLCA
return left if left else right
例:
3
/ \
5 1
/ \ / \
6 2 0 8
/ \
7 4
p=5, q=1 → LCA = 3
p=5, q=4 → LCA = 5
問題 6: 二分木の直列化・逆直列化（LeetCode 297）— 上級
class Codec:
def serialize(self, root) -> str:
"""BFSを使ってツリーを文字列に直列化"""
if not root:
return ""
result = []
queue = deque([root])
while queue:
node = queue.popleft()
if node:
result.append(str(node.val))
queue.append(node.left)
queue.append(node.right)
else:
result.append("null")
return ",".join(result)
def deserialize(self, data: str):
"""直列化された文字列からツリーを復元"""
if not data:
return None
values = data.split(",")
root = TreeNode(int(values[0]))
queue = deque([root])
i = 1
while queue:
node = queue.popleft()
if i < len(values) and values[i] != "null":
node.left = TreeNode(int(values[i]))
queue.append(node.left)
i += 1
if i < len(values) and values[i] != "null":
node.right = TreeNode(int(values[i]))
queue.append(node.right)
i += 1
return root
**時間計算量:** O(n)
**空間計算量:** O(n)
2. Binary Search Tree（BST）パターン
BSTの特性
- 左サブツリーの全ての値は現在のノードより小さい
- 右サブツリーの全ての値は現在のノードより大きい
- 中順巡回でソート順に訪問できる
問題 7: 有効なBSTの検証（LeetCode 98）
def isValidBST(root) -> bool:
def validate(node, min_val, max_val):
if not node:
return True
if node.val <= min_val or node.val >= max_val:
return False
return (validate(node.left, min_val, node.val) and
validate(node.right, node.val, max_val))
return validate(root, float('-inf'), float('inf'))
落とし穴: 単に left.val < root.val < right.val のみを確認するのは誤り
無効なBSTの例:
5
/ \
1 4
/ \
3 6
root.right.left = 3（3 < 5はBST違反）
問題 8: BST内のK番目に小さい要素（LeetCode 230）
def kthSmallest(root, k: int) -> int:
count = [0]
result = [0]
def inorder(node):
if not node or count[0] >= k:
return
inorder(node.left)
count[0] += 1
if count[0] == k:
result[0] = node.val
return
inorder(node.right)
inorder(root)
return result[0]
反復方式（より直感的）
def kthSmallestIterative(root, k: int) -> int:
stack = []
current = root
while current or stack:
while current:
stack.append(current)
current = current.left
current = stack.pop()
k -= 1
if k == 0:
return current.val
current = current.right
return -1
問題 9: ソート済み配列をBSTに変換（LeetCode 108）
def sortedArrayToBST(nums: list[int]):
def buildBST(left, right):
if left > right:
return None
バランスを保つために中間値をルートとして選択
mid = left + (right - left) // 2
root = TreeNode(nums[mid])
root.left = buildBST(left, mid - 1)
root.right = buildBST(mid + 1, right)
return root
return buildBST(0, len(nums) - 1)
3. グラフ BFS/DFS パターン
グラフの表現
隣接リスト（推奨）
graph = {
0: [1, 2],
1: [0, 3],
2: [0, 4],
3: [1],
4: [2]
}
隣接行列
matrix = [
[0, 1, 1, 0, 0],
[1, 0, 0, 1, 0],
[1, 0, 0, 0, 1],
[0, 1, 0, 0, 0],
[0, 0, 1, 0, 0]
]
標準テンプレート
DFS（再帰）
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
for neighbor in graph[start]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
BFS
def bfs(graph, start):
visited = {start}
queue = deque([start])
while queue:
node = queue.popleft()
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
問題 10: 島の数（LeetCode 200）
def numIslands(grid: list[list[str]]) -> int:
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
count = 0
def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == '0':
return
grid[r][c] = '0' # 訪問済みマーク
dfs(r + 1, c)
dfs(r - 1, c)
dfs(r, c + 1)
dfs(r, c - 1)
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1':
count += 1
dfs(r, c)
return count
例:
grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
出力: 3
**時間計算量:** O(m*n)
**空間計算量:** O(m*n)（再帰スタック）
問題 11: グラフのクローン（LeetCode 133）
class Node:
def __init__(self, val=0, neighbors=None):
self.val = val
self.neighbors = neighbors if neighbors is not None else []
def cloneGraph(node):
if not node:
return None
cloned = {} # 元のノード → クローンのマッピング
def dfs(original):
if original in cloned:
return cloned[original]
copy = Node(original.val)
cloned[original] = copy
for neighbor in original.neighbors:
copy.neighbors.append(dfs(neighbor))
return copy
return dfs(node)
**時間計算量:** O(V + E)
**空間計算量:** O(V)
問題 12: コーススケジュール（LeetCode 207）— トポロジカルソート
前提条件の関係が与えられたとき、全コースを受講できるか判定せよ。
from collections import defaultdict, deque
def canFinish(numCourses: int, prerequisites: list[list[int]]) -> bool:
graph = defaultdict(list)
in_degree = [0] * numCourses
for course, prereq in prerequisites:
graph[prereq].append(course)
in_degree[course] += 1
入次数が0のノードからスタート（前提条件なし）
queue = deque([i for i in range(numCourses) if in_degree[i] == 0])
completed = 0
while queue:
course = queue.popleft()
completed += 1
for next_course in graph[course]:
in_degree[next_course] -= 1
if in_degree[next_course] == 0:
queue.append(next_course)
return completed == numCourses
DFSによるサイクル検出
def canFinishDFS(numCourses: int, prerequisites: list[list[int]]) -> bool:
graph = defaultdict(list)
for course, prereq in prerequisites:
graph[prereq].append(course)
状態: 0=未訪問, 1=訪問中, 2=完了
state = [0] * numCourses
def hasCycle(node):
if state[node] == 1: # サイクル検出
return True
if state[node] == 2: # 処理済み
return False
state[node] = 1
for neighbor in graph[node]:
if hasCycle(neighbor):
return True
state[node] = 2
return False
for i in range(numCourses):
if hasCycle(i):
return False
return True
問題 13: 太平洋・大西洋への水流（LeetCode 417）
def pacificAtlantic(heights: list[list[int]]) -> list[list[int]]:
if not heights:
return []
rows, cols = len(heights), len(heights[0])
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
def bfs(starts):
visited = set(starts)
queue = deque(starts)
while queue:
r, c = queue.popleft()
for dr, dc in directions:
nr, nc = r + dr, c + dc
if (0 <= nr < rows and 0 <= nc < cols and
(nr, nc) not in visited and
heights[nr][nc] >= heights[r][c]): # 逆方向探索
visited.add((nr, nc))
queue.append((nr, nc))
return visited
太平洋（上端 + 左端）
pacific_starts = [(0, c) for c in range(cols)] + [(r, 0) for r in range(1, rows)]
大西洋（下端 + 右端）
atlantic_starts = [(rows-1, c) for c in range(cols)] + [(r, cols-1) for r in range(rows-1)]
pacific = bfs(pacific_starts)
atlantic = bfs(atlantic_starts)
return [[r, c] for r, c in pacific & atlantic]
問題 14: 単語はしご（LeetCode 127）
beginWordからendWordへの最短変換経路を求めよ。
def ladderLength(beginWord: str, endWord: str, wordList: list[str]) -> int:
word_set = set(wordList)
if endWord not in word_set:
return 0
queue = deque([(beginWord, 1)])
visited = {beginWord}
while queue:
word, steps = queue.popleft()
for i in range(len(word)):
for c in 'abcdefghijklmnopqrstuvwxyz':
new_word = word[:i] + c + word[i+1:]
if new_word == endWord:
return steps + 1
if new_word in word_set and new_word not in visited:
visited.add(new_word)
queue.append((new_word, steps + 1))
return 0
例:
beginWord = "hit", endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]
出力: 5（hit -> hot -> dot -> dog -> cog）
**時間計算量:** O(M^2 _ N) — Mは単語長、Nは辞書サイズ
**空間計算量:** O(M^2 _ N)
4. Union Find（素集合データ構造）パターン
実装
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
経路圧縮
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py:
return False # 既に同じ集合
ランクによる合併
if self.rank[px] < self.rank[py]:
px, py = py, px
self.parent[py] = px
if self.rank[px] == self.rank[py]:
self.rank[px] += 1
return True
def connected(self, x, y):
return self.find(x) == self.find(y)
問題 15: 連結コンポーネントの数（LeetCode 323）
def countComponents(n: int, edges: list[list[int]]) -> int:
uf = UnionFind(n)
components = n
for u, v in edges:
if uf.union(u, v):
components -= 1 # 2つのコンポーネントが合併
return components
問題 16: 冗長な辺（LeetCode 684）
削除するとツリーになる辺を見つけよ。
def findRedundantConnection(edges: list[list[int]]) -> list[int]:
n = len(edges)
uf = UnionFind(n + 1)
for u, v in edges:
if not uf.union(u, v):
return [u, v] # 既に接続済み → 冗長な辺
return []
問題 17: アカウントのマージ（LeetCode 721）
def accountsMerge(accounts: list[list[str]]) -> list[list[str]]:
email_to_id = {}
email_to_name = {}
for i, account in enumerate(accounts):
name = account[0]
for email in account[1:]:
if email not in email_to_id:
email_to_id[email] = len(email_to_id)
email_to_name[email] = name
uf = UnionFind(len(email_to_id))
for account in accounts:
first_email = account[1]
first_id = email_to_id[first_email]
for email in account[2:]:
uf.union(first_id, email_to_id[email])
from collections import defaultdict
groups = defaultdict(list)
for email, eid in email_to_id.items():
root = uf.find(eid)
groups[root].append(email)
result = []
for root, emails in groups.items():
name = email_to_name[emails[0]]
result.append([name] + sorted(emails))
return result
5. 最短経路アルゴリズム
Dijkstraのアルゴリズム
負の重みがないグラフで単一始点最短経路を求めます。
from collections import defaultdict
def dijkstra(graph: dict, start: int) -> dict:
distances = {node: float('inf') for node in graph}
distances[start] = 0
pq = [(0, start)] # （距離, ノード）
while pq:
current_dist, current_node = heapq.heappop(pq)
より短い経路が既に見つかっている場合はスキップ
if current_dist > distances[current_node]:
continue
for neighbor, weight in graph[current_node]:
distance = current_dist + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(pq, (distance, neighbor))
return distances
**時間計算量:** O((V + E) log V)
**空間計算量:** O(V)
問題 18: ネットワーク遅延時間（LeetCode 743）
def networkDelayTime(times: list[list[int]], n: int, k: int) -> int:
graph = defaultdict(list)
for u, v, w in times:
graph[u].append((v, w))
distances = {i: float('inf') for i in range(1, n + 1)}
distances[k] = 0
pq = [(0, k)]
while pq:
dist, node = heapq.heappop(pq)
if dist > distances[node]:
continue
for neighbor, weight in graph[node]:
new_dist = dist + weight
if new_dist < distances[neighbor]:
distances[neighbor] = new_dist
heapq.heappush(pq, (new_dist, neighbor))
max_dist = max(distances.values())
return max_dist if max_dist != float('inf') else -1
例:
times = [[2,1,1],[2,3,1],[3,4,1]], n=4, k=2
出力: 2
問題 19: K回以内の経由地での最安フライト（LeetCode 787）
Bellman-Ford変形でK回以内の経由地での最低コストを求めます。
def findCheapestPrice(n: int, flights: list[list[int]], src: int, dst: int, k: int) -> int:
Bellman-Ford: k+1回緩和
prices = [float('inf')] * n
prices[src] = 0
for i in range(k + 1):
temp = prices.copy() # 各反復の更新を分離
for u, v, w in flights:
if prices[u] != float('inf') and prices[u] + w < temp[v]:
temp[v] = prices[u] + w
prices = temp
return prices[dst] if prices[dst] != float('inf') else -1
例:
n=3, flights=[[0,1,100],[1,2,100],[0,2,500]], src=0, dst=2, k=1
出力: 200（0 -> 1 -> 2）
6. 企業別のツリー・グラフ出題傾向
Googleは**グラフ問題を非常に頻繁に**出題します。
- 頻出: グラフ探索、トポロジカルソート、最短経路
- 重視: 効率的なアルゴリズム選択と計算量分析
- 例題: Course Schedule II、Word Ladder、Alien Dictionary
Meta（Facebook）
Metaは**ツリー巡回とLCA**問題を好みます。
- 頻出: Binary Tree、LCA、直列化/逆直列化
- 重視: 再帰と反復の両方で実装できること
- 例題: Binary Tree Right Side View、Vertical Order Traversal
Amazon
Amazonは**BFSと最短経路**問題を多く出題します。
- 頻出: Number of Islands、BFS変形、Union Find
- 重視: 実用的で効率的な解法
- 例題: Rotting Oranges、Find if Path Exists in Graph
7. 練習問題クイズ
二分木で任意の2ノード間の最長経路（辺数）を求めよ。経路はルートを通らなくてもよい。
**答え**: DFSで各ノードの左右の最大深度の和を計算し、グローバル最大値を更新します。
**解説**:
def diameterOfBinaryTree(root) -> int:
max_diameter = [0]
def depth(node):
if not node:
return 0
left_depth = depth(node.left)
right_depth = depth(node.right)
現在ノードを通る経路の直径
max_diameter[0] = max(max_diameter[0], left_depth + right_depth)
return 1 + max(left_depth, right_depth)
depth(root)
return max_diameter[0]
グラフ `{0: [1], 1: [2], 2: [0], 3: [4], 4: []}` にサイクルはあるか？
**答え**: あり（0 -> 1 -> 2 -> 0）
**解説**: DFSと3色マーキング（0=未訪問、1=訪問中、2=完了）を使います。訪問中のノードに再度到達した場合、サイクルがあります。
def hasCycle(graph):
state = {}
def dfs(node):
if state.get(node) == 1:
return True
if state.get(node) == 2:
return False
state[node] = 1
for neighbor in graph.get(node, []):
if dfs(neighbor):
return True
state[node] = 2
return False
return any(dfs(node) for node in graph if node not in state)
BSTとターゲットkが与えられたとき、合計がkになる2ノードの値が存在するか判定せよ。
**答え**: 中順巡回でソートされた値を取得した後、Two Pointersを適用します。
**解説**:
def findTarget(root, k: int) -> bool:
def inorder(node):
if not node:
return []
return inorder(node.left) + [node.val] + inorder(node.right)
nums = inorder(root)
left, right = 0, len(nums) - 1
while left < right:
total = nums[left] + nums[right]
if total == k:
return True
elif total < k:
left += 1
else:
right -= 1
return False
二値グリッドで1で繋がった島の中で最大の面積を求めよ。
**答え**: DFS/BFSで各島の面積を計算し、最大値を返します。
**解説**:
def maxAreaOfIsland(grid):
rows, cols = len(grid), len(grid[0])
def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == 0:
return 0
grid[r][c] = 0 # 訪問済みマーク
return 1 + dfs(r+1,c) + dfs(r-1,c) + dfs(r,c+1) + dfs(r,c-1)
return max(dfs(r, c) for r in range(rows) for c in range(cols) if grid[r][c])
Union Findを使ってn個の都市を最小コストで接続するアルゴリズムを実装せよ（LeetCode 1584）。
**答え**: 全辺をコスト昇順にソートし、Union Findでサイクルを作らずに辺を追加します。
**解説**:
def minCostConnectPoints(points):
n = len(points)
edges = []
for i in range(n):
for j in range(i + 1, n):
dist = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])
edges.append((dist, i, j))
edges.sort()
uf = UnionFind(n)
total_cost = 0
edges_used = 0
for cost, u, v in edges:
if uf.union(u, v):
total_cost += cost
edges_used += 1
if edges_used == n - 1:
break
return total_cost
まとめ
ツリーとグラフはFAANG面接で最も多様なパターンが登場する分野です。重要な判断基準:
- **BFS vs DFS の選択**: 最短経路 → BFS、全経路探索 → DFS
- **ツリー問題**: 再帰が自然な場合が多いが、反復も準備する
- **グラフ問題**: visited処理を常に明確にする
- **Union Find**: 連結性問題で非常に強力なツール
**おすすめLeetCode問題リスト:**
- Easy: Maximum Depth、Invert Tree、Symmetric Tree
- Medium: Course Schedule、Number of Islands、LCA、BFS/DFS変形
- Hard: Serialize/Deserialize、Word Ladder II、Alien Dictionary
현재 단락 (1/597)
ツリーとグラフの問題はFAANG面接において、配列・文字列に次いで出題頻度が高い分野です。特にGoogleとMetaはグラフとツリーの探索問題を非常に重視します。本記事では面接必須の5つの核心パターン...