今日の記録 2020/7/7

勉強した

みんなのデータ構造 - P125 問6.8

昨日の続きで実装を考えていたのだがつまってしまった。まず以下のツリー構造で考える。

{ id0,
   { id1, { id2, nil, nil }, {id3, nil, nil} } }
   { id4, { id5, nil, nil }, {id6, nil, nil} }

これの preOrder の実装を考えていたのだが、 id3 の preOrder は id4 になるのだが、これを見つけるためには stack を使った方法ぐらいしか思いつかず、 O(1) でこれを実装する方法が分からなかった。

この問題には大分時間を使ったので、諦めて答えを探してみたのだが見つけられなかった。練習問題の答えどこかに上げられてないだろうか。