题目
给定一个 N 叉树，返回其节点值的 后序遍历 。
N 叉树 在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。
示例 1：
输入：root = [1,null,3,2,4,null,5,6] 输出：[5,6,3,2,4,1]
示例 2：
输入：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]
解题
方法一：递归
/* // 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: void postorder(Node* root,vector<int>& res){ if(!root) return; for(Node* child:root->children){ postorder(child,res); } res.push_back(root->val); } vector<int> postorder(Node* root) { vector<int> res; postorder(root,res); return res; } };
方法二：迭代
根据前序遍历的思想, 中右左----reverse–>左右中，就是后序遍历了。
/* // 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) { if(!root) return {}; vector<int> res; stack<Node*> stack; stack.push(root); while(!stack.empty()){ Node* cur=stack.top(); stack.pop(); res.push_back(cur->val); //pop出来的顺序为中右左 最后reverse成左右中 for(Node* child:cur->children){ stack.push(child); } } reverse(res.begin(),res.end()); return res; } };
