給定一個 N 叉樹，返回其節(jié)點值的后序遍歷。
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

首先采用遞歸法，假設當前節(jié)點不為空
遍歷所有孩子節(jié)點，向每個孩子節(jié)點進行遞歸
遞歸后，存入當前節(jié)點的值。和前序遍歷僅相差在存入節(jié)點的代碼位置

遞歸法具體代碼

vector<int> res; // 結果集
vector<int> postorder(Node* root) {
    if(root == NULL){ //判斷當前節(jié)點不為空
        return res;
    }
    for(int i = 0; i < root->children.size(); i++){ //遍歷所有孩子節(jié)點
        postorder(root->children[i]); //遞歸進入孩子節(jié)點
    }
    res.push_back(root->val); //將當前節(jié)點加入結果集
    return res; //返回結果
}

思路2

使用迭代法，不使用遞歸調用的方式。
使用棧來輔助，我們一層一層進行遍歷
假設此時我們在處理第n行的節(jié)點p1
先把p1的所有兄弟節(jié)點（p2，p3，p4，...）存入棧中，等待后續(xù)使用
接著把p1存入結果集中，遍歷p1所有孩子節(jié)點（pc1，pc2，...），存入棧中，等待后續(xù)使用
取出p1的最左孩子節(jié)點pc1，依次往下處理，假設此時p1的所有孩子節(jié)點都處理完畢了
從棧中取出p2，以此類推使用。
因此整個棧的存放順序為
棧底|pn, pn-1,...,p2,pcn,...,pc2,pc1
也就是說，存棧的時候，局部逆序存儲

和遞歸法不同，迭代法的迭代過程中，其實我們是不知道什么時候p1的孩子節(jié)點全部遍歷完，開始遍歷p2的
所以需要在棧中，額外壓入p1的位置，并使用第二個棧，用來存儲暫時不存入結果集的根節(jié)點
整個棧的存放順序為
孩子棧棧底|pn,pn-1,...,p2,p1,pcn,...pc2,pc1
根節(jié)點棧棧底|p,p1

迭代法具體代碼

vector<int> res;
stack<Node*> s_child;
stack<Node*> s_root;
vector<int> postorder(Node* root) {
    while(root != NULL){ // 該判斷用來規(guī)避初始為空的情況
        if(root->children.size()){ //根節(jié)點處理
            s_root.push(root);  //根節(jié)點存入根節(jié)點棧
            s_child.push(root); //根節(jié)點臨時存入孩子節(jié)點棧
            //存入所有孩子節(jié)點
            for(int i = root->children.size() - 1; i >= 0; i--){
                s_child.push(root->children[i]);
            }
        }
        else{ //葉子節(jié)點，直接存入結果集
            res.push_back(root->val);
        }

        //取出棧頂值
        if(s_child.empty()){ //全部取完，結束
            break;
        }
        root = s_child.top();
        s_child.pop();

        //如果當前節(jié)點為預存的根節(jié)點
        while(root == s_root.top()){
            res.push_back(root->val);  //存入結果集
            s_root.pop();              //根節(jié)點棧彈出一個元素
            if(s_child.empty()){       //遍歷完成則break
                break;
            }
            root = s_child.top();      //否則再次取棧頂
            s_child.pop();
        }
        if(s_child.empty()){           //若是break離開while循環(huán)的，結束遍歷
            break;                     //可能出現(xiàn)的情況是：最后一個根節(jié)點輸出完畢時
        }
    }
    return res;
}