590.N叉树的后序遍历

链接：590.N叉树的后序遍历
难度：Easy
标签：栈、树、深度优先搜索
简介：给定一个 N 叉树，返回其节点值的后序遍历。

题解 1 - java

• 编辑时间：2020-02-21
• 执行用时：1ms
• 内存消耗：41.7MB
• 编程语言：java
• 解法介绍：遍历每个子节点再递归。

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;
    public Node() {}
    public Node(int _val) {
        val = _val;
    }
    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
	LinkedList<Integer> list = new LinkedList<Integer>();
    public List<Integer> postorder(Node root) {
    	inPostorder(root);
        return list;
    }
    void inPostorder(Node node) {
    	if(node==null)return;
    	if(node.children!=null)
    	for(int i=0,len=node.children.size();i<len;i++) {
    		inPostorder(node.children.get(i));
    	}
		list.add(node.val);
    }
}

题解 2 - python

• 编辑时间：2024-02-19
• 执行用时：53ms
• 内存消耗：18.12MB
• 编程语言：python
• 解法介绍：dfs。

class Solution:
    def postorder(self, root: 'Node') -> List[int]:
        if not root: return []
        return reduce(lambda arr, cur: arr + cur, [self.postorder(child) for child in root.children], []) + [root.val] 

题解 3 - cpp

• 编辑时间：2022-03-12
• 执行用时：20ms
• 内存消耗：12.1MB
• 编程语言：cpp
• 解法介绍：迭代。

class Solution {
   public:
    vector<int> postorder(Node *root) {
        vector<int> ans;
        stack<Node *> s;
        unordered_set<Node *> sset;
        if (root) s.push(root);
        while (s.size()) {
            Node *node = s.top();
            s.pop();
            if (sset.count(node)) {
                ans.push_back(node->val);
                continue;
            }
            sset.insert(node);
            s.push(node);
            for (auto it = node->children.rbegin(); it != node->children.rend();
                 it++) {
                s.push(*it);
            }
        }
        return ans;
    }
};

题解 4 - cpp

• 编辑时间：2022-03-12
• 执行用时：16ms
• 内存消耗：11.3MB
• 编程语言：cpp
• 解法介绍：dfs。

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