LeetCode C++ 590. N-ary Tree Postorder Traversal【Tree/DFS】简单
发布日期:2021-07-01 02:53:06
浏览次数:3
分类:技术文章
本文共 1705 字,大约阅读时间需要 5 分钟。
Given an n-ary tree, return the postorder traversal of its nodes' values.
Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).
Follow up:
Recursive solution is trivial, could you do it iteratively?
Example 1:
Input: root = [1,null,3,2,4,null,5,6]Output: [5,6,3,2,4,1]
Example 2:
Input: 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]Output: [2,6,14,11,7,3,12,8,4,13,9,10,5,1]
Constraints:
- The height of the n-ary tree is less than or equal to
1000
- The total number of nodes is between
[0, 10^4]
题意:给定一个 N
叉树,返回其节点值的后续遍历。
思路1 递归后序遍历
class Solution { public: vector ans; void postorderTraversal(Node* root) { if (root) { for (Node *&it : root->children) postorderTraversal(it); ans.push_back(root->val); } } vector postorder(Node* root) { postorderTraversal(root); return ans; }};
效率如下:
执行用时:56 ms, 在所有 C++ 提交中击败了33.29% 的用户内存消耗:11.5 MB, 在所有 C++ 提交中击败了41.71% 的用户
思路2 非递归后序遍历
使用简易版(双栈法)非递归后序遍历,代码如下:
class Solution { public: vector postorder(Node* root) { if (root == nullptr) return { }; vector ans; stackst; st.push(root); while (!st.empty()) { Node* t = st.top(); st.pop(); ans.push_back(t->val); for (Node* child : t->children) st.push(child); } reverse(ans.begin(), ans.end()); return ans; }};
效率如下:
执行用时:44 ms, 在所有 C++ 提交中击败了75.95% 的用户内存消耗:11.3 MB, 在所有 C++ 提交中击败了85.25% 的用户
转载地址:https://memcpy0.blog.csdn.net/article/details/108942017 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
初次前来,多多关照!
[***.217.46.12]2024年04月11日 17时16分44秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
安装Samba时遇到错误
2019-05-02
详细解析Java中抽象类和接口的区别
2019-05-02
Linux下的同步与异步
2019-05-02
Ajax中的XMLHttpRequest对象详解
2019-05-02
GDB命令大全
2019-05-02
IT行业培训必读:优秀程序员的十个习惯
2019-05-02
实例属性和类属性
2019-05-02
StringIO和BytesIO
2019-05-02
财务分析与决策:同型分析
2019-05-02
今日整理PDF电子书资料
2019-05-02
【语言-c#】C# 超级整数计算
2019-05-02
【软件-Doxgen】工具:程序代码生成xml文档(doxgen)
2019-05-02
【框架-MFC】CMFCMenuBar 菜单按钮的图标添加
2019-05-02
【语言-c#】C# 注释详细介绍说明
2019-05-02
MySQL 内存模型
2019-05-02
express 解析post方式下的json参数
2019-05-02