Erklärung dieser Bedingung im Binärbaum

Question

Ich habe ein Programm online gefunden, das einen Binärbaum in der Ebenenreihenfolge durchläuft. Der Code unten geht und erzeugt die gewünschte Ausgabe:

class Solution { 
public: 

    std::vector< vector<int>> res; 

    void buildVec(TreeNode* root, int level) { 
     if(root==NULL) 
      return; 
     if(res.size()==level) 
      res.push_back(vector<int>()); 

     res[level].push_back(root->val); 
     buildVec(root->left, level+1); 
     buildVec(root->right, level+1); 
    } 

    vector<vector<int>> levelOrder(TreeNode* root) { 
     res.clear(); 
     buildVec(root, 0); 
     return res; 
    } 
}; 

Was ich nicht verstehe, ist die Aussage: if(res.size()==level). Was genau erreicht diese Aussage? Wenn der Level 2 ist, kann es (maximal) 4 Elemente geben (da Level mit 0 beginnen), was größer ist als der Wert von Label (2). Also, wie funktioniert diese Aussage?

Edit: Also, wenn der Eingang:

3 
/\ 
9 20 
/\ 
    15 7 

dann wieder der Ausgang wäre

[ 
    [3], 
    [9,20], 
    [15,7], 
] 

Answer 1

Der Grund ist es der zweite rekursive Aufruf buildVec zu vermeiden, ist eine weitere hinzufügen zu müssen level-vector zum Ende des Ergebnisvektors, obwohl der erste Aufruf bereits einen für diese bestimmte Ebene hinzugefügt hat.

Am einfachsten ist es, herauszufinden, was von sich geht ein Beispiel zu tun auf Ihrem Beispiel Baum laufen, ohne 15 und 7.

Das erste, was levelOrder tut, ist leer die res Vektor. Dann ruft es buildVec(root, 0). In dort root ist nicht gleich NULL, aber es gilt res.size() = 0 = level, so wird ein leerer Vektor an res, also res = [[]] angehängt. Im nächsten Schritt wird der Wert des aktuellen Knotens in den neu angehängten Vektor geschoben. Also res = [[3]].

Dann wird buildVec(root->left, 1) aufgerufen. Dort ist wiederum root nicht NULL, sondern res.size() = 1 = level, daher wird ein weiterer leerer Vektor an res angehängt, also res = [[3], []]. Wir fügen den Wert 9 in res[1] ein, also jetzt res = [[3], [9]].

Beim Aufruf buildVec(root->left, 2) und buildVec(root->right, 2) passiert nichts, weil beide Kinder nicht existieren, d. H. In diesen Aufrufen root == NULL gibt True zurück.

Also fahren wir mit dem Anruf fort. Hier, zum ersten Mal, res.size() = 2 != 1 = level. Also fügen wir keinen neuen Vektor an. Dann fügen wir den Wert 20 in res[1] ein. Also res = [[3], [9, 20]].

Wäre der Check res.size() == level nicht da, hätten wir am Ende einen neuen leeren Vektor angehängt, so wäre das Ergebnis stattdessen res = [[3], [9, 20], []] gewesen.

Aber wie sich herausstellt, ist die Prüfung falsch. Wenn Sie den Baum zu

 3 
/ \ 
    20 9 
/\ 
15 7 

Flip wird es [[3], [20, 9], [15, 7], []] zurück. Die korrekte Überprüfung ist res.size() <= level.

Answer 2

if(res.size()==level) 
    res.push_back(vector<int>()); 

Diese Aussage ist nur ein weiterer Vektor in die res für eine neue Ebene hinzuzufügen.

3 
/\ 
9 20 
/\ 
    15 7 

der für den Knoten 15 der Ebene nehmen lassen 2 sein wird.

der Wert res wird [[3], [9, 20]] und res.size() == 2, wird die Bedingung wahr sein, so dass es einen neuen Vektor für neue Ebene schaffen und den Knoten 15 darin, wieder für den Knoten 7 die Bedingung wird, da die res.size() falsch einsetzen wird wird 3, so wird der Knoten in den Vektor res[level] eingefügt, ohne den neuen Vektor zu erzeugen.