In Bezug auf Preorder Baum-Traversal

Question

ich den folgenden Code-Snippet für rekursive Binary Tree Vorordnungsdurchquerung geschrieben haben:

/** 
* Definition for a binary tree node. 
* struct TreeNode { 
*  int val; 
*  TreeNode *left; 
*  TreeNode *right; 
*  TreeNode(int x) : val(x), left(NULL), right(NULL) {} 
* }; 
*/ 
class Solution { 
private: 
    std::vector<int> myVec; 
public: 
    vector<int> preorderTraversal(TreeNode* root) { 
     if(root==NULL) 
      return vector<int>(); 

     myVec.push_back(root->val); 
     preorderTraversal(root->left); 
     preorderTraversal(root->right); 

     return myVec; 
    } 
}; 

Während dieser Code ausgeführt wird und erzeugt die erwartete Leistung, ich bin nicht ganz sicher, ob dies richtig ist; denn wenn ich preorderTraversal(root->left); und preorderTraversal(root->right); rufe, verwende ich nicht die Werte, die sie zurückgeben (vector<int> s). Also,

1. Ist das korrekt?
2. Wenn nein, wie kann ich diesen Code dann korrigieren?

Answer 1

Ja, es ist korrekt, wenn Sie es einmal anrufen. Wenn nicht, wird myVec Vektor nicht gelöscht.

In der Tat, jeder Aufruf an preorderTraversal, mit Ausnahme der oberen und Pfad von ihm nach links, zurück einige Zwischenzustand, die nicht viel Sinn macht. Wenn ich Sie wäre, würde ich diesen Code Refactoring den Zwischenwert innerhalb der Klasse zu verstecken:

class Solution { 
private: 
    std::vector<int> myVec; 

    void traverse(TreeNode* root) { 
     if (root == NULL) 
      return; 

     myVec.push_back(root->val); 
     preorderTraversal(root->left); 
     preorderTraversal(root->right); 
    } 

public: 
    vector<int> preorderTraversal(TreeNode* root) { 
     myVec.clear(); 
     traverse(root); 
     return myVec; 
    } 
};