590. N叉树的后序遍历

给定一个 N 叉树，返回其节点值的后序遍历。
N叉树的定义如下

class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};

例如

给定一个 3叉树 :

    1
   /|\
  3 2 4
 / \
5  6

返回其后序遍历: [5,6,3,2,4,1]。

说明:

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

思路1

首先采用递归法，假设当前节点不为空
遍历所有孩子节点，向每个孩子节点进行递归
递归后，存入当前节点的值。和前序遍历仅相差在存入节点的代码位置

递归法具体代码

vector<int> res; // 结果集
vector<int> postorder(Node* root) {
    if(root == NULL){ //判断当前节点不为空
        return res;
    }
    for(int i = 0; i < root->children.size(); i++){ //遍历所有孩子节点
        postorder(root->children[i]); //递归进入孩子节点
    }
    res.push_back(root->val); //将当前节点加入结果集
    return res; //返回结果
}

思路2

使用迭代法，不使用递归调用的方式。
使用栈来辅助，我们一层一层进行遍历
假设此时我们在处理第n行的节点p1
先把p1的所有兄弟节点（p2，p3，p4，...）存入栈中，等待后续使用
接着把p1存入结果集中，遍历p1所有孩子节点（pc1，pc2，...），存入栈中，等待后续使用
取出p1的最左孩子节点pc1，依次往下处理，假设此时p1的所有孩子节点都处理完毕了
从栈中取出p2，以此类推使用。
因此整个栈的存放顺序为
栈底|pn, pn-1,...,p2,pcn,...,pc2,pc1
也就是说，存栈的时候，局部逆序存储

和递归法不同，迭代法的迭代过程中，其实我们是不知道什么时候p1的孩子节点全部遍历完，开始遍历p2的
所以需要在栈中，额外压入p1的位置，并使用第二个栈，用来存储暂时不存入结果集的根节点
整个栈的存放顺序为
孩子栈栈底|pn,pn-1,...,p2,p1,pcn,...pc2,pc1
根节点栈栈底|p,p1

迭代法具体代码

vector<int> res;
stack<Node*> s_child;
stack<Node*> s_root;
vector<int> postorder(Node* root) {
    while(root != NULL){ // 该判断用来规避初始为空的情况
        if(root->children.size()){ //根节点处理
            s_root.push(root);  //根节点存入根节点栈
            s_child.push(root); //根节点临时存入孩子节点栈
            //存入所有孩子节点
            for(int i = root->children.size() - 1; i >= 0; i--){
                s_child.push(root->children[i]);
            }
        }
        else{ //叶子节点，直接存入结果集
            res.push_back(root->val);
        }

        //取出栈顶值
        if(s_child.empty()){ //全部取完，结束
            break;
        }
        root = s_child.top();
        s_child.pop();

        //如果当前节点为预存的根节点
        while(root == s_root.top()){
            res.push_back(root->val);  //存入结果集
            s_root.pop();              //根节点栈弹出一个元素
            if(s_child.empty()){       //遍历完成则break
                break;
            }
            root = s_child.top();      //否则再次取栈顶
            s_child.pop();
        }
        if(s_child.empty()){           //若是break离开while循环的，结束遍历
            break;                     //可能出现的情况是：最后一个根节点输出完毕时
        }
    }
    return res;
}