Drei Arten von Baumdurchquerungen sind inorder, preorder und post order.
Eine vierte, weniger häufig verwendete Traversierung ist die Level-Order-Traversierung. In einem level-order travesal, alle Knoten in Tiefe "d" werden vorher bearbeitet jeder Knoten in der Tiefe d + 1. Die Durchquerung der Ebenenreihenfolge unterscheidet sich von der anderen Traversalen, dass es nicht rekursiv gemacht wird; eine Warteschlange wird verwendet, anstelle des impliziten Rekursionsstapels.
Meine Fragen zum obigen Textausschnitt sind
Danke!
Ebenenreihenfolge-Traversal ist eigentlich eine BFS , das von Natur aus nicht rekursiv ist. Es verwendet Warteschlange anstelle von Stack , um die nächsten Scheitelpunkte zu speichern, die geöffnet werden sollen. Der Grund dafür ist, dass Sie in dieser Traversierung die Knoten in einer FIFO Reihenfolge öffnen möchten, anstatt einer LIFO Reihenfolge, erhalten durch Rekursion
Wie ich bereits erwähnt habe, ist die Ebenenreihenfolge tatsächlich ein BFS, und sein [BFS] -Pseudocode [aus Wikipedia] lautet:
%Vor%(*) In einem Baum wird das Markieren der Scheitelpunkte nicht benötigt, da Sie nicht in zwei verschiedenen Pfaden zum selben Knoten gelangen können.
Anstelle einer Warteschlange habe ich eine Karte verwendet, um das Problem zu lösen. Schauen Sie, wenn Sie interessiert sind. Während ich eine Postorder-Traversierung durchführe, behalte ich die Tiefe bei, in der jeder Knoten positioniert ist, und verwende diese Tiefe als Schlüssel in einer Map, um Werte auf derselben Ebene zu sammeln
class Solution {
public:
map<int, vector<int> > levelValues;
void recursivePrint(TreeNode *root, int depth){
if(root == NULL)
return;
if(levelValues.count(root->val) == 0)
levelValues.insert(make_pair(depth, vector<int>()));
levelValues[depth].push_back(root->val);
recursivePrint(root->left, depth+1);
recursivePrint(root->right, depth+1);
}
vector<vector<int> > levelOrder(TreeNode *root) {
recursivePrint(root, 1);
vector<vector<int> > result;
for(map<int,vector<int> >::iterator it = levelValues.begin(); it!= levelValues.end(); ++it){
result.push_back(it->second);
}
return result;
}
};
Die gesamte Lösung finden Sie hier - Ссылка Die Lösung gibt einen Vektorenvektor zurück, wobei jeder innere Vektor die Elemente im Baum in der richtigen Reihenfolge enthält.
Sie können versuchen, es hier zu lösen - Ссылка
Und wie Sie sehen, können wir das auch rekursiv in der gleichen Zeit und Komplexität wie die Queue-Lösung machen!
Tags und Links algorithm