【力ボタン】589.Nフォークツリーの前順遍歴

テーマの概要
原題リンクは1つのNフォークツリーを与えて、そのノードの値の前の順序を返して遍歴して、Nフォークツリーノードは以下のように定義します:

class Node {
     
public:
    int val;
    vector<Node*> children;

    Node() {
     }

    Node(int _val) {
     
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
     
        val = _val;
        children = _children;
    }
};

思考過程.
再帰法
ツリーの遍歴問題は基本的に再帰的に実現でき、再帰的な実現には3つの点を考慮する必要がある.

再帰終了条件

再帰の戻り値

再帰ごとに処理する必要があること

では、Nフォークツリーに戻って遍歴すると、二フォークツリーに比べて、ルートノードの個数が左右の子供から多くの子供に変わったにほかならない.Nフォークツリー遍歴では、N人の子供をどのように除去するかを考えるだけでよい.ノード定義から分かるように、N人の子供はvector配列に格納されているので、主はfor を利用してN人の子供を取り出す必要がある.コードは以下の通りである.

   void dfs(Node* root, vector<int>& vt) {
     
       //       ：     
       if (root == NULL) return ;
       //           ：               
       //            ：vt  
       vt.push_back(root->val);
       vector<Node*> child = root->children;
       for(auto c:child) dfs(c, vt);
   }

   vector<int> preorder(Node* root) {
     
       vector<int> ans;
       dfs(root, ans);

       return ans;
   }

反復法
同様に二叉木から考えると,stack を用いて前順遍歴と後順遍歴を実現できる.

まず極端な状況を考慮する:ルートノードが空->空の結果配列

を直接返す.

は、処理するノードを格納するためのstackを作成し、まず

にノードを追加する.

は、while の制御を用いる、stackが空でない場合、循環処理

を行う.

は、現在のノード(stackのスタックトップ要素)へのNodeポインタを作成し、そのノード値を最終出力vectorに加え、スタックからスタックトップ要素

を削除する.

stackの先進的な後出特性に基づいて、現在のノードの最後の子供を先に加入する必要があり、最後に最初の子供を加入してこそ、データを取り出す際に前順遍歴の要求

に達することができる. 5には、コードなどの2つの実装形態がある.
法一:2つのスタックを使用する

   vector<int> preorder(Node* root) {
     
       vector<int> vt;
       if (root == NULL) return vt;

       stack<Node*> node;
       node.push(root);
       while (!node.empty()) {
     
           Node* cur = node.top();
           node.pop();
           vt.push_back(cur->val);
           vector<Node*> child = cur->children;
           stack<Node*> temp;
           for (auto c:child) temp.push(c);
           while(!temp.empty()) {
     
               node.push(temp.top());
               temp.pop();
           }
       }

       return vt;
   }

法二:スタックを使用する

   vector<int> preorder(Node* root) {
     
       vector<int>  vt;
       if (root == NULL) return vt;
       stack<Node*> st;
       st.push(root);
       while(!st.empty()) {
     
           Node* cur = st.top();
           st.pop();
           vt.push_back(cur->val);
           for(int i = cur->children.size() - 1; i >= 0; i--) {
     
               st.push(cur->children[i]);
           }
       }
       return vt;
   }