就職面接で以下の質問をされました。
ルート ノード (適切に形成されたバイナリ ツリーへのノード) と他の 2 つのノード (ツリー内に存在することが保証されており、異なるものである) が与えられると、2 つのノードの最も低い共通の祖先を返します。
最小共通祖先アルゴリズムを知らなかったので、その場で作ってみました。次のコードを作成しました。
def least_common_ancestor(root, a, b):
lca = [None]
def check_subtree(subtree, lca=lca):
if lca[0] is not None or subtree is None:
return 0
if subtree is a or subtree is b:
return 1
else:
ans = sum(check_subtree(n) for n in (subtree.left, subtree.right))
if ans == 2:
lca[0] = subtree
return 0
return ans
check_subtree(root)
return lca[0]
class Node:
def __init__(self, left, right):
self.left = left
self.right = right
次のテスト ケースを試したところ、期待どおりの答えが得られました。
a = Node(None, None)
b = Node(None, None)
tree = Node(Node(Node(None, a), b), None)
tree2 = Node(a, Node(Node(None, None), b))
tree3 = Node(a, b)
しかし、私のインタビュアーは、「あなたのアルゴリズムが None を返す木のクラスがある」と言いました。私はそれが何なのか理解できず、インタビューに失敗しました。アルゴリズムが 2 になることなくツリーの最下部に到達するケースは考えられません。ans何が欠けているのでしょうか?