改善したい動作を理解するために、再帰の問題が何であるかを述べていません。
これには多くの解決策がありますが、ほとんどすべての解決策で、再帰的な解決策と同じか、パフォーマンスが低下します。実際、最善の解決策は、ツリーを作成するときに行う必要があることです。たとえば、各ノードの高さをノードごとに 4 番目の配列インデックスに格納できます。次に、最大の高さを見つけるために、4 つおきのインデックスを簡単にスキャンします。また、高さチェック中に計算する必要がないように、ノードに親参照が保存されていると簡単になります。
1 つの解決策は、スタックを使用して再帰をシミュレートすることですが、それは実際には再帰と変わりません。
別の解決策は、各ノードを調べて、その親に基づいてその高さを決定することですが、特定のトラバーサルの順序ではありません。ただし、これをどのように構成したかにより、階層を格納するためのセカンダリ データ構造がないため、O(n^2) の効率が低下します。問題は、配列全体をスキャンしないと、子から親に到達できないことです。次に、線形時間で実行できます（ただし、再帰も線形時間であるため、改善されているかどうかはわかりません。メモリの観点からも、それほど改善されるわけではありません）。
改善したい効率の種類を定義できますか?
それぞれの疑似コードは次のとおりですが、簡単には存在しないいくつかのデータ構造に依存しています。
「再帰なしの再帰」ソリューション：
int get_height(int * tree, int length) {
Stack stack;
int max_height = 0;
if (length == 0) {
return 0;
}
// push an "array" of the node index to process and the height of its parent.
// make this a struct and use that for real c code
stack.push(0,0);
while(!stack.empty()) {
int node_index, parent_height = stack.pop();
int height = parent_height + 1;
if (height > max_height) {
max_height=height;
}
if (tree[node_index+1] != 0 )
stack.push(tree[node_index+1], height);
if (tree[node_index+2] != 0 )
stack.push(tree[node_index+2], height);
}
return max_height;
}
現在、追加のメモリを使用しない非常に遅いソリューションに取り組んでいますが、それは本当に悪いです。フィボナッチを再帰的に悪いと書くようなものです。元のアルゴリズムは各ノードを通過し、O(n^2) の実行時間に対して O(n) チェックを実行しました (実際には、当初考えていたほど悪くはありません)。
編集：ずっと後、子を持つすべてのノードをスキップする最適化を追加しています。これは、多くの通話をカットするので、非常に重要です。最良のケースは、ツリーが実際にリンクされたリストである場合です。この場合、O(n) 時間で実行されます。最悪の場合は、完全にバランスの取れたツリーです。それぞれの logn リーフ ノードが O((log(n)^2) のルートに戻って logn チェックを行います。これはそれほど悪くはありません。以下の行はそのようにマークされます。
「本当に遅いが余分なメモリがない」ソリューション（ただし、それほど遅くないように更新されました）：
int get_height(int * tree, int length) {
int max_height = 0;
for (int i = 0; i < length; i+=3) {
// Optimization I added later
// if the node has children, it can't be the tallest node, so don't
// bother checking from here, as the child will be checked
if (tree[i+1] != 0 || tree[i+2] != 0)
continue;
int height = 0;
int index_pointing_at_me;
// while we haven't gotten back to the head of the tree, keep working up
while (index_pointing_at_me != 0) {
height += 1;
for (int j = 0; j < length; j+=3) {
if (tree[j+1] == tree[i] ||
tree[j+2] == tree[i]) {
index_pointing_at_me = j;
break;
}
}
}
if (height > max_height) {
max_height = height;
}
}
return max_height;
}
以前のソリューションを改善しましたが、O(n) メモリを使用します。これは、配列内で親が常に子の前にあることを前提としています (技術的には必要ないと思います)。
int get_height(int * tree, int length) {
if (length == 0)
return 0;
// two more nodes per node - one for which node is its parent, the other for its height
int * reverse_mapping = malloc((sizeof(int) * length / 3) * 2)
reverse_mapping[1] = 1; // set height to 1 for first node
// make a mapping from each node to the node that points TO it.
// for example, for the first node
// a[0] = 32
// a[1] = 3
// a[2] = 6
// store that the node at 3 and 6 are both pointed to by node 0 (divide by 3 just saves space since only one value is needed) and that each child node is one taller than its parent
int max_height = 0;
for (int i = 0; i < length; i+=3) {
int current_height = reverse_mapping[(i/3)*2+1];
if (current_height > max_height)
max_height = current_height;
reverse_mapping[(tree[i+1]/3)*2] = i;
reverse_mapping[(tree[i+1]/3)*2 + 1] = current_height + 1;
reverse_mapping[(tree[i+2]/3)*2] = i;
reverse_mapping[(tree[i+2]/3)*2 + 1] = current_height + 1;
}
return max_height
}