【dfs】590. N 叉树的后序遍历

来源：易妖游戏网

题目

给定一个 n 叉树的根节点 root ，返回其节点值的后序遍历。

n 叉树在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。

进阶：递归法很简单，你可以使用迭代法完成此题吗?

答案

暴力解法

/*
// 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) { //迭代 先序遍历入栈
        stack<Node*> buf;
        //stack<int> output;
        vector<int> ans;
        if(root!=NULL)
            buf.push(root);

        while(!buf.empty()) {
            Node* tmp = buf.top();
            ans.push_back(tmp->val);
            buf.pop();

            for(int i = 0; i < tmp->children.size(); i++) {
                buf.push(tmp->children[i]);
            }
            
        }

        reverse(ans.begin(), ans.end());

        return ans;
    }
};

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文

全部频道

【dfs】590. N 叉树的后序遍历

题目

答案

暴力解法