589.N叉树的前序遍历

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

题解 1 - java

• 编辑时间：2020-02-21
• 执行用时：1ms
• 内存消耗：41.2MB
• 编程语言：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> preorder(Node root) {
    	if(root==null)return list;
    	inPreorder(root);
		return list;
    }
    void inPreorder(Node node) {
    	list.add(node.val);
    	for(int i=0,len=node.children.size();i<len;i++) {
    		inPreorder(node.children.get(i));
    	}
    }
}

题解 2 - cpp

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

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

题解 3 - cpp

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

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

题解 4 - python

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

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