Preorder, Postorder, Inorder Traversal
以下はいずれもDFSの再帰関数で結構シンプルに実装できる preorder traversal
postorder traversal
stackを使って実装できる
inorder traversal
数式でいえば
人間に馴染み深い 1 + (2 - 3)みたいな記法
前者2つの方法だとカッコがいらない
数字や演算子をスタックに置く順番で指定できてるから.
再帰関数がシンプルだけど、二分木に存在するノードが膨大なケースもある
処理されるループが深すぎてstack overflowする可能性が出てくる
その場合
再帰ではなくwhile等で実装することになる
その他、参考