589.N叉树的前序遍历

2024-05-15 00:44

文章标签 遍历前序 589

本文主要是介绍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）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。