N叉树的前序遍历和后序遍历代码非常相似,只需要修改将val放入res数组的位置即可。
需要注意的两点:
多叉树遍历需要使用一个map来记录,已经遍历到了第几个孩子节点。
1.这个map记录的是,哪个节点已经访问到第几个子节点了。
unordered_map也可以用地址作为key。
2.多叉树遍历的过程中,pop *** 作是在当前节点的所有子节点访问结束之后才可以pop。
class Solution {
public:
vector<int> postorder(Node* root) {
vector<int> res;
if (root == nullptr) {
return res;
}
unordered_map<Node *, int> cnt;
stack<Node *> st;
Node * node = root;
while (!st.empty() || node != nullptr) {
while (node != nullptr) {
st.emplace(node);
if (node->children.size() > 0) {
cnt[node] = 0;
node = node->children[0];
} else {
node = nullptr;
}
}
node = st.top();
int index = cnt.count(node) ? (cnt[node] + 1) : 0;
if (index < node->children.size()) {
cnt[node] = index;
node = node->children[index];
} else {
res.emplace_back(node->val);
st.pop();
cnt.erase(node);
node = nullptr;
}
}
return res;
}
};
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)