590.N-Ary Tree Postorder Traversal

发表于 | 分类于 ， | 评论数： | 阅读次数：
字数统计: 382 | 阅读时间 ≈ 2

题目描述

我的解法

解题思路

递归

树的后序遍历，递归的方法和前序的类似，只不过需要调换下递归调用的顺序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
public:
    void postorder_traverse(vector<int>& nums, Node* tree_node){
        for (auto iter : tree_node -> children)
            postorder_traverse(nums, iter);
        nums.push_back(tree_node -> val);
    }
    vector<int> postorder(Node* root) {
        vector<int> nums;
        if (root == NULL) return nums;
        postorder_traverse(nums, root);
        return nums;
    }
};

Runtime: 100 ms, faster than 12.21% of C++ online submissions for N-ary Tree Postorder Traversal.
Memory Usage: 56.7 MB, less than 20.00% of C++ online submissions for N-ary Tree Postorder Traversal.

迭代

迭代的方法也和前序的类似，不过for的时候是要从前到后，因为最后的时候要把整个数组翻转过来，所以要让右边的最先pop出来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
public:
    vector<int> postorder(Node* root) {
        vector<int> nums;
        if (root == NULL) return nums;
        stack<Node*> s;
        s.push(root);
        while(!s.empty()){
            Node* tmp = s.top();
            s.pop();
            nums.push_back(tmp -> val);
            for (int i = 0; i < tmp -> children.size(); i++)
                s.push(tmp -> children[i]);
        }
        reverse(nums.begin(), nums.end());
        return nums;
    }
};

Runtime: 60 ms, faster than 84.99% of C++ online submissions for N-ary Tree Postorder Traversal.
Memory Usage: 56.5 MB, less than 20.00% of C++ online submissions for N-ary Tree Postorder Traversal.