スタックの中順の走査で二分探索木の k 番目に小さい値を探す - LeetCode 230

二分探索木から、小さい方から数えて k 番目の値を返します。左、自分、右の順に読むと小さい順になることを使い、その読み方を再帰ではなくスタックの繰り返しで書く練習です。

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

問題

二分探索木の根 root と、整数 k を受け取ります。木の値を小さい順に並べたとき、前から数えて k 番目 (1 から数える) の値を返す関数を書いてください。

  • 二分探索木では、どの節でも、左の部分木の値はすべてその節より小さく、右の部分木の値はすべてその節より大きくなっています
  • 各節は val、left、right を持ちます。Go の節は TreeNode で、Val、Left、Right です
  • 節の数を n とすると、n は 1 以上 500 以下、k は 1 以上 n 以下です。値はどれも違い、-10000 以上 10000 以下です
  • 木を再帰でたどらず、自分で用意したスタックを使った繰り返しで書いてください

例では、木を上の段から左の順に読んだ値の並びで書きます。子が無いところは null です。

入力と出力の例

例 1

小さい順に並べると 1、3、4、6、9、11 です。3 番目は 4 です。

入力

root = [6, 3, 9, 1, 4, null,
  11]
k = 3

出力

4

例 2

2 の右に 3 がぶら下がった木です。小さい順は 2、3、5、8 で、4 番目は 8 です。

入力

root = [5, 2, 8, null, 3]
k = 4

出力

8

例 3

節が 1 つだけの木です。

入力

root = [7]
k = 1

出力

7

図で見る

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

面接での聞かれ方

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

  • 「二分探索木の中で、k 番目に小さい値を返してください」
  • 値を全部集めて並べ替える書き方を答えると、「二分探索木の決まりを使えていますか?」「k が小さいとき、全部読む必要がありますか?」と聞き返されます
  • 「再帰を使わずに書けますか?」と、繰り返しの書き方を求められることもあります

二分探索木の問題では、「左、自分、右の順に読むと小さい順になる」と最初に言えるかで、その先の会話が変わります。

ヒント

まだ開いていません

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

  1. ヒント 2

  2. ヒント 3

  3. ヒント 4答えに近い

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

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

main.py
def kth_in_bst(root: TreeNode | None, k: 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(kth_in_bst(build_tree([6, 3, 9, 1, 4, None, 11]), 3))

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