589.N叉树的前序遍历

刷算法题：

第一遍：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）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。