admin 管理员组

文章数量: 1086864

[LeetCode] N

 

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

For example, given a 3-ary tree:

 

 

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

 

参考资料：

/

 

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

本文标签： LeetCode N

版权声明：本文标题：[LeetCode] N 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/b/1693650910a234679.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。