LeetCode 590. N叉树的后序遍历（后序遍历）

1. 题目

2. 解题

2.1 递归

代码语言：javascript复制

class Solution {
public:
    vector<int> postorder(Node* root) {
        vector<int> ans;
        postRec(root, ans);
        return ans;
    }

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

2.2 循环

• 利用先序，改一下，得到 根右左，最后反转 左右根（后序）

代码语言：javascript复制

class Solution {
public:
    vector<int> postorder(Node* root) {
        if(root == NULL)
        	return {};
        vector<int> ans;
        stack<Node*> stk;
        stk.push(root);
        Node *tp;
        int i, k;
        while(!stk.empty())
        {
        	tp = stk.top();
        	k = tp->children.size();
        	ans.push_back(tp->val);
        	stk.pop();
        	i = 0;
        	while(i<k)
        		stk.push(tp->children[i  ]);
        }
        //上面得到的是根右左，逆序return得到左右根(后序)
        return vector<int> (ans.rbegin(), ans.rend());
    }
};

递归

0 人点赞