题目描述
给定一个 n 叉树,返回其节点值的前序遍历。
例如,给定一个 3 叉树
:
返回其前序遍历: [5,6,3,2,4,1]
。
说明
- 递归法很简单,你可以使用迭代法完成此题吗?
算法
(栈模拟递归) $O(n)$
- 参考 题解 LeetCode 589 。
- 这里唯一的区别就是结点记录的时机。这里记录的时机为遍历完所有儿子结点之后。
时间复杂度
- 每个结点均摊遍历常数次,故时间复杂度也为 $O(n)$。
空间复杂度
- 由于使用了栈来存储中间结点,所以空间复杂度为 $O(n)$。
C++ 代码
/*
// 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> ans;
if (!root)
return ans;
stack<pair<Node*, int>> st;
st.push(make_pair(root, 0));
while (!st.empty()) {
auto cur = st.top();
st.pop();
if (cur.second < cur.first -> children.size()) {
st.push(make_pair(cur.first, cur.second + 1));
st.push(make_pair(cur.first -> children[cur.second], 0));
} else {
ans.push_back(cur.first -> val);
}
}
return ans;
}
};