並べ替えられたリンク リストから BST を作成したいと考えています。私は問題を再帰的に解決しましたが、問題の複雑さを変えずに同じ問題の反復的な解決策を書く方法を考えていました。
[編集]
注: 独自のスタックを実装したくありません。
[編集2]
自分自身を再帰的に呼び出す関数は f です。疑似コードを以下に示します。からのヘッドポインタで f を呼び出しますmain
node * f(int start_index, int end_index, node *ptr) {
if ( start>end) return NULL
middle_index = start_index + (end_index-start_index)/2
node *l_child = f(start_index, middle_index-1, ptr)
initialize parent with ptr's value
parent->left = l_child
ptr = ptr->next
parent->right = f(middle_index+1, end, ptr)
return parent
}