# LeetCode Easy 590. N-ary Tree Postorder Traversal

tags: leetcode

問題

• Explore
• Problems

アイデア

おさらいをすると二分木の場合はPreorder, Inorder, Postorder traversalはそれぞれ根のノードがいつ探索されるかで分類されており，

• Preorder(根→左→右)
• Inorder(左→根→右)
• Postorder(左→右→根)

今回は2つより多くの子を持つ木に関してその探索を実装をします．

解法1(recursive)

Preorderは根から見て，子の見ていきました．

Postorderは子から見て，根を見ます．

計算量

ノードの数を$N$とする．

• 時間計算量
  • $O(N)$
• 空間計算量
  • 再帰の深さで必要なのは平均$O(\log N)$で最悪$O(N)$
  • 答えの配列に必要なのは$O(N)$
  • 全体だと$O(N)$だが，配列がない場合はiterativeに書くべし

C++

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
public:
  vector<int> postorder(Node* root) {
    vector<int> res;
    addNodes(root, res);
    return res;
  }
private:
  void addNodes(Node* node, vector<int>& res) {
    if (!node)
      return;
    for (auto& child : node->children)
      addNodes(child, res);
    res.push_back(node->val);
  }
};

解法2(iterative)

暇になったら書きます