leetcode第590题N叉树的后序遍历

给定一个 N 叉树，返回其节点值的 后序遍历 。
N 叉树 在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。
进阶：

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

示例 ：

590.png

输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出：[2,6,14,11,7,3,12,8,4,13,9,10,5,1]

1. N叉树的数据结构定义如下，节点中包含多个子节点组成的vector数组。

// 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;
    }
};

2. 递归算法
   递归算法理解起来比较简单，在遍历根节点时，首先递归遍历其子节点，最后遍历根节点。

    void innerPostOrder(Node *root, vector<int> &vec) {
        if (root == nullptr) {
            return;
        }
        for (int i = 0; i < root->children.size(); ++i) {
            innerPostOrder(root->children[i], vec);
        }
        vec.push_back(root->val);
    }

3. 迭代算法
   按照N叉树后序遍历的具体算法执行过程，访问某个节点时，首先访问其子节点，最后才访问根节点。所以，我们想到需要使用堆栈保存根节点。
   进栈： 首次访问节点时，push进栈，并将其子节点也一并进栈。
   出栈： 当某个节点是叶子节点（没有子节点）时需要出栈。
   非叶子节点出栈：需要判断其所有子节点都已被访问，我们定义一个临时指针，保存上次出栈的节点。当上一个出栈节点为其最后一个子节点，那么就可以继续对非叶子节点进行出栈操作。

    void stackPostOrder(Node *root, vector<int> &vec) {
        if (root == nullptr) {
            return;
        }
        stack<Node *> st;
        st.push(root);
        Node *last = nullptr;
        while (!st.empty()) {
            Node *p = st.top();
            int size = p->children.size();
            if (size == 0 || p->children[size - 1] == last) {
                vec.push_back(p->val);
                last = p;
                st.pop();
                continue;
            }
            for (int i = size; i > 0; --i) {
                st.push(p->children[i - 1]);
            }
        }
    }

4. 完整实现如下

class Solution {
public:
    vector<int> postorder(Node* root) {
        vector<int> ret;
        // innerPostOrder(root, ret);
        stackPostOrder(root, ret);
        return ret;
    }

    void innerPostOrder(Node *root, vector<int> &vec) {
        if (root == nullptr) {
            return;
        }
        for (int i = 0; i < root->children.size(); ++i) {
            innerPostOrder(root->children[i], vec);
        }
        vec.push_back(root->val);
    }

    void stackPostOrder(Node *root, vector<int> &vec) {
        if (root == nullptr) {
            return;
        }
        stack<Node *> st;
        st.push(root);
        Node *last = nullptr;
        while (!st.empty()) {
            Node *p = st.top();
            int size = p->children.size();
            if (size == 0 || p->children[size - 1] == last) {
                vec.push_back(p->val);
                last = p;
                st.pop();
                continue;
            }
            for (int i = size; i > 0; --i) {
                st.push(p->children[i - 1]);
            }
        }
    }
};