# LeetCode Easy 589. N-ary Tree Preorder Traversal
tags: leetcode
最近カップ中本にハマってしまいました.
問題
アイデア
おさらいをすると二分木の場合はPreorder, Inorder, Postorder traversalはそれぞれ根のノードがいつ探索されるかで分類されており,
- Preorder(根→左→右)
- Inorder(左→根→右)
- Postorder(左→右→根)
今回は2つより多くの子を持つ木に関してその探索を実装をします.
N-ary木にはPreorderとPostorderだけが定義されていて,やることは同じです.
解法1(recursive)
ノードから伸びるノードの配列に対して再帰的に関数を実行します.
それぞれ値を答えの配列に格納するだけです.
計算量
ノードの数を$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> preorder(Node* root) { vector<int> res; addNodes(root, res); return res; } private: void addNodes(Node* node, vector<int>& res) { if (!node) return; res.push_back(node->val); for (auto& child : node->children) addNodes(child, res); } };
解法2(iterative)
暇が出来たらやります()
Stackを使えば出来ます