[LeetCode] N-ary Tree Postorder Traversal N叉树的后序遍历

时间:2022-09-09 23:18:26

Given an n-ary tree, return the postorder traversal of its nodes' values.

For example, given a 3-ary tree:

[LeetCode] N-ary Tree Postorder Traversal N叉树的后序遍历

Return its postorder traversal as: [5,6,3,2,4,1].

Note:

Recursive solution is trivial, could you do it iteratively?

这道题让我们求N叉树的后序遍历,由于有了之前那道 Binary Tree Postorder Traversal 的基础,了解了二叉树的后序遍历,则N叉树的后序遍历也就没有那么难了。首先还是用递归来做,在递归函数中,判空后,遍历子结点数组,对所有的子结点调用递归函数,然后在 for 循环之外在将当前结点值加入结果 res 数组,这样才能保证是后序遍历的顺序,参见代码如下:

解法一:

class Solution {
public:
vector<int> postorder(Node* root) {
vector<int> res;
helper(root, res);
return res;
}
void helper(Node* node, vector<int>& res) {
if (!node) return;
for (Node* child : node->children) {
helper(child, res);
}
res.push_back(node->val);
}
};

我们也可以使用迭代的方法来做,这里有个小 trick,写法跟先序遍历十分的像,不同的就是每次把从 stack 中取的结点的值都加到结果 res 的最前面,还有就是遍历子结点数组的顺序是正常的顺序,而前序遍历是从子结点数组的后面往前面遍历,这点区别一定要注意,参见代码如下:

解法二:

class Solution {
public:
vector<int> postorder(Node* root) {
if (!root) return {};
vector<int> res;
stack<Node*> st{{root}};
while (!st.empty()) {
Node *t = st.top(); st.pop();
res.insert(res.begin(), t->val);
for (Node* child : t->children) {
if (child) st.push(child);
}
}
return res;
}
};

类似题目:

Binary Tree Postorder Traversal

N-ary Tree Preorder Traversal

N-ary Tree Level Order Traversal

参考资料:

https://leetcode.com/problems/n-ary-tree-preorder-traversal/

https://leetcode.com/problems/n-ary-tree-postorder-traversal/discuss/147959/Java-Iterative-and-Recursive-Solutions

LeetCode All in One 题目讲解汇总(持续更新中...)

[LeetCode] N-ary Tree Postorder Traversal N叉树的后序遍历的更多相关文章

  1. leetcode 590&period;N-ary Tree Postorder Traversal N叉树的后序遍历

    递归方法 C++代码: /* // Definition for a Node. class Node { public: int val; vector<Node*> children; ...

  2. leetcode 题解&colon;Binary Tree Preorder Traversal (二叉树的先序遍历)

    题目: Given a binary tree, return the preorder traversal of its nodes' values. For example:Given binar ...

  3. LeetCode 145 Binary Tree Postorder Traversal(二叉树的兴许遍历)&plus;(二叉树、迭代)

    翻译 给定一个二叉树.返回其兴许遍历的节点的值. 比如: 给定二叉树为 {1. #, 2, 3} 1 \ 2 / 3 返回 [3, 2, 1] 备注:用递归是微不足道的,你能够用迭代来完毕它吗? 原文 ...

  4. LeetCode 590&period; N叉树的后序遍历&lpar;N-ary Tree Postorder Traversal&rpar;

    590. N叉树的后序遍历 590. N-ary Tree Postorder Traversal 题目描述 给定一个 N 叉树,返回其节点值的后序遍历. LeetCode590. N-ary Tre ...

  5. LeetCode:N叉树的后序遍历【590】

    LeetCode:N叉树的后序遍历[590] 题目描述 给定一个 N 叉树,返回其节点值的后序遍历. 例如,给定一个 3叉树 : 返回其后序遍历: [5,6,3,2,4,1]. 题目分析 这道题有好几 ...

  6. Java实现 LeetCode 590 N叉树的后序遍历(遍历树,迭代法)

    590. N叉树的后序遍历 给定一个 N 叉树,返回其节点值的后序遍历. 例如,给定一个 3叉树 : 返回其后序遍历: [5,6,3,2,4,1]. 说明: 递归法很简单,你可以使用迭代法完成此题吗? ...

  7. C&num;LeetCode刷题之&num;590-N叉树的后序遍历(N-ary Tree Postorder Traversal)

    问题 该文章的最新版本已迁移至个人博客[比特飞],单击链接 https://www.byteflying.com/archives/4092 访问. 给定一个 N 叉树,返回其节点值的后序遍历. 例如 ...

  8. &lpar;二叉树 递归&rpar; leetcode 145&period; Binary Tree Postorder Traversal

    Given a binary tree, return the postorder traversal of its nodes' values. Example: Input: [1,null,2, ...

  9. C&plus;&plus;版 - LeetCode 145&colon; Binary Tree Postorder Traversal&lpar;二叉树的后序遍历,迭代法&rpar;

    145. Binary Tree Postorder Traversal Total Submissions: 271797 Difficulty: Hard 提交网址: https://leetco ...

随机推荐

  1. css例子

    6.背景图像渐变的制作body{ background:#ccc url(xxx.gif)rpeat-x或y:} 7.给一个区块加上背景#branding{ width:700px: height:2 ...

  2. 传说中的AutoCAD公司 - 欧特克(Autodesk)招聘开发顾问-上海或北京

    如果您热衷新技术,垂涎科技前沿,对编程有*的热情,乐于帮助别人打造解决方案,喜爱分享和交流,英文沟通无障碍,来吧,把简历丢过来! 如果您刚毕业不久,那也不要因为工作经历尚浅而怯步,我们也非常欢迎您! ...

  3. MySQL主从读写分离专题

    主机A:192.168.1.101从机B:192.168.1.102 1.先登录主机 Amysql>GRANT REPLICATION SLAVE ON *.* TO slave_user@19 ...

  4. 购买SSD固态硬盘须当心,你知道什么是SLC、 MLC、TLC闪存芯片颗粒吗?

    固态硬盘凭借其存取速率超快等自身优势,被越来越多的电脑爱好者所青睐,并迅速普及到了广大用户的电脑中,因为固态硬盘与传统机械硬盘相比,确实在运行效率等方面有了质的提升,但是亦是美网络小编要提醒大家的是, ...

  5. 纯css 构造的tip

    css部分: <style>   .abc{ margin-top:20px; } span{ position:relative; display: inline-block; back ...

  6. Tinyhttpd精读解析

    首先,本人刚刚开始开源代码精读,写的不对的地方,大家轻拍,一起进步.本文是对Tinyhttpd的一次精读,大家每天都在用着http服务,很多人也一直活跃在上层,使用IIS.Apache等,大家是否想看 ...

  7. 走进JavaScript

    JavaScript的作用:操作HTML元素,响应用户的操作,处理数据: script标签的type或者language可以写也可以不写: script标签防止位置:head结束之前或者body结束之 ...

  8. LeetCode&colon;114&lowbar;Flatten Binary Tree to Linked List &vert; 将一棵二叉树变成链表的形式 &vert; Medium

    要求:Given a binary tree, flatten it to a linked list in-place.将二叉树转化为平坦序列的树.比如: 结题思路: 该题有个提示,转化后的树的序列 ...

  9. Eclipse构建项目时&quot&semi;An internal error occurred during&colon; &quot&semi;Building workspace&quot&semi;&period; Java heap space&quot&semi;

    出现这个错误,eclipse 会卡死,以及自动退出 解决方案 工程根目录 找到项目中.project文件 删除这两处   第一处:  <buildCommand>          &lt ...

  10. 使用InstallUtil安装或卸载服务

    使用InstallUtil安装或卸载服务 一.安装服务: C:\Windows\Microsoft.NET\Framework\v4.0.30319\InstallUtil.exe D:\MyServ ...