难度:Easy
给定一个 N 叉树,返回其节点值的后序遍历。
例如,给定一个 3叉树 :
返回其后序遍历: [5,6,3,2,4,1].
说明: 递归法很简单,你可以使用迭代法完成此题吗?
递归法:
/*// Definition for a Node.class Node {public:int val;vector<Node*> children;Node() {}Node(int _val, vector<Node*> _children) {val = _val;children = _children;}};*/class Solution {public:vector<int> postorder(Node* root) {vector<int>res;if(!root) return res;for(auto i:root->children){vector<int>tmp =postorder(i);res.insert(res.end(),tmp.begin(),tmp.end());}res.push_back(root->val);return res;}};
迭代法:
/*// Definition for a Node.class Node {public:int val;vector<Node*> children;Node() {}Node(int _val, vector<Node*> _children) {val = _val;children = _children;}};*/class Solution {public:vector<int> postorder(Node* root) {vector<int>res;if(!root) return res;stack<Node*>pt;pt.push(root);while(!pt.empty()){if(pt.top()->children.empty()){res.push_back(pt.top()->val);pt.pop();if(!pt.empty()) pt.top()->children.erase(pt.top()->children.begin());}else{pt.push(pt.top()->children[0]);}}return res;}};