再帰で二分木の 2 つの節にいちばん近い共通の祖先を探す - LeetCode 236

二分木の中の 2 つの値について、両方を下に持つ節のうち、いちばん深い節の値を返します。左右の部分木から見つけた物を上へ返し、両側から返った所で答えを決める再帰の練習です。

海外で定番の問題リスト 4 本のうち 2 本に入っています (Grind 75、LeetCode Top Interview 150)

問題

二分木の根 root と、木の中にある 2 つの値 p と q を受け取ります。値が p の節と値が q の節の、いちばん近い共通の祖先の値を返す関数を書いてください。

  • 共通の祖先は、2 つの節の両方を自分の下に持つ節です。ここでは、節は自分自身の祖先でもあると数えます。そのため、片方がもう片方の祖先なら、上にあるほうが答えです
  • いちばん近い共通の祖先は、共通の祖先のうちいちばん深い (根から遠い) 節です
  • 木は二分探索木とは限りません。値の大きさで左右を決めることはできません
  • 木の値はどれも違います。p と q は違う値で、どちらも必ず木の中にあります
  • 返すのは節ではなく、その節の値です
  • 各節は val (値)、left (左の子)、right (右の子) を持ちます。子が無いところは、Python では None、JavaScript では null、Go では nil です。Go の節は TreeNode で、Val、Left、Right と大文字で始まります
  • 節の数は 2 以上 500 以下、値はどれも -1000 以上 1000 以下です

例では、木を上の段から左の順に読んだ値の並びで書きます。子が無いところは null です。例 1 と例 2 は同じ木です。根が 6、その下が 15 と 3、15 の下が 7 と 11、3 の右が 9、11 の下が 2 と 13 です。

入力と出力の例

例 1

2 は 11 の下、7 は 15 のすぐ下にあります。両方を下に持ついちばん深い節は 15 です。

入力

root = [6, 15, 3, 7, 11,
  null, 9, null, null, 2, 13]
p = 2
q = 7

出力

15

例 2

13 は 11 の子です。11 は自分自身の祖先でもあるので、答えは 11 です。

入力

root = [6, 15, 3, 7, 11,
  null, 9, null, null, 2, 13]
p = 11
q = 13

出力

11

例 3

-4 は根の左の下、8 は根の右にあります。左右に分かれているので、根の 0 が答えです。

入力

root = [0, -5, 8, null, -4]
p = -4
q = 8

出力

0

図で見る

例 1 で、解き方がどう動くか。押すと大きく開きます。

面接での聞かれ方

面接では、短く次のように渡されることが多いです。

  • 「二分木の 2 つの節の、いちばん近い共通の祖先を返してください」
  • 書き始める前に「片方が見つからないことはありますか?」「値が重なることはありますか?」と条件を確かめると、よい印象になります
  • 書き終えたあとに「片方が木に無いかもしれないなら、どこを変えますか?」「二分探索木なら、もっと速くできますか?」と広げて聞かれます
  • 「各節が親へのつながりを持っていたらどう解きますか?」と、データの持ち方を変えて聞かれることもあります

この再帰は「両方が必ず木にある」ことに頼っています。最初にこの条件を確かめて口に出しておきます。

ヒント

まだ開いていません

付箋は 4 枚。下の段ほど答えに近づきます

  1. ヒント 2

  2. ヒント 3

  3. ヒント 4答えに近い

アルゴリズムのチートシートの「再帰と木」に、この型の要点を表とコードでまとめています。

再帰は、同じ形の小さい問題に分けて自分を呼ぶ書き方です。木の深さや、全部の組み合わせを数える問題で使います。

main.py
def common_ancestor(root: TreeNode | None, p: int, q: int) -> int:
    """
    Goal: 何を返すか

    idea1: まず思いつく案
    -> runtime: O(?)  space: O(?)

    idea2: もっと速い案
    -> runtime: O(?)  space: O(?)

    edge case: 空、1 つだけ、など
    """
    # 節は root.val、root.left、root.right のように点で読みます。空きは None です
    # ここに書きます
    pass


# 「実行」を押すと、この行の結果が出ます
# build_tree は、例と同じ並びから木を組みます
print(common_ancestor(build_tree([6, 15, 3, 7, 11, None, 9, None, None, 2, 13]), 2, 7))

できているか「例で確かめる」を押すと、問題の例を全部この関数に渡して、通ったかをここに出します