刷算法題：

第一遍：1.看5分鐘，沒思路看題解

2.通過題解改進自己的解法，并且要寫每行的注釋以及自己的思路。

3.思考自己做到了題解的哪一步，下次怎么才能做對(總結方法)

4.整理到自己的自媒體平臺。

5.再刷重復的類似的題目，根據時間和任務安排刷哪幾個板塊

6.用c++語言 都刷過一遍了 就刷中等

一.題目

給定一個 n?叉樹的根節點??root?，返回?其節點值的?前序遍歷?。

n 叉樹 在輸入中按層序遍歷進行序列化表示，每組子節點由空值?null?分隔（請參見示例）。

示例 1：

輸入：root = [1,null,3,2,4,null,5,6]
輸出：[1,3,5,6,2,4]

示例 2：

輸入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
輸出：[1,2,3,6,7,11,14,4,8,12,5,9,13,10]

提示：

• 節點總數在范圍?[0, 104]內
• 0 <= Node.val <= 104
• n 叉樹的高度小于或等于?1000

進階：遞歸法很簡單，你可以使用迭代法完成此題嗎?

二、反思

1.自己的解法

/*
// 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;helper(root,res);return res;}void helper(Node* root,vector<int> & res){if(root==nullptr){return ;}res.emplace_back(root->val);for(auto & ch:root->children){helper(ch,res);}}
};

2.題目的解法?

class Solution {
public:vector<int> preorder(Node* root) {vector<int> res;if (root == nullptr) {return res;}unordered_map<Node *, int> cnt;stack<Node *> st;Node * node = root;while (!st.empty() || node != nullptr) {while (node != nullptr) {res.emplace_back(node->val);st.emplace(node);if (node->children.size() > 0) {cnt[node] = 0;node = node->children[0];} else {node = nullptr;}         }node = st.top();int index = (cnt.count(node) ? cnt[node] : -1) + 1;if (index < node->children.size()) {cnt[node] = index;node = node->children[index];} else {st.pop();cnt.erase(node);node = nullptr;}}return res;}
};作者：力扣官方題解
鏈接：https://leetcode.cn/problems/n-ary-tree-preorder-traversal/solutions/1317175/n-cha-shu-de-qian-xu-bian-li-by-leetcode-bg99/
來源：力扣（LeetCode）
著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。

?3.思路的異同

一種是迭代的方法，一種是遞歸的方法，遞歸的方法，其實和二叉樹是一樣，只不過把左右節點的遞歸寫成了利用for循環的方式，通用的數據入vector的位置依然是對應前序中序后序。

三.進步的地方

?會一個題也就會了一類題，接下來的這段時間就開始復習了。