题目描述
给定一个 n 叉树,返回其节点值的前序遍历。
例如,给定一个 3 叉树
:
返回其前序遍历: [1,3,5,6,2,4]
。
说明
- 递归法很简单,你可以使用迭代法完成此题吗?
算法
(栈模拟递归) $O(n)$
- 这里采用一个通用的树结构遍历递归转非递归的做法。
- 迭代法实现前序遍历需要一个栈来存储当前路径上的结点,每个元素为一个二元组(结点指针,遍历过的儿子结点的数量)。
- 初始时,根结点(
root
,0
)入栈。如果遍历过的儿子结点数量为 0,则记录当前值。然后判断是否存在下一个儿子结点,如果存在,则当前结点(结点指针,遍历过的儿子结点的数量 + 1)再次入栈,然后儿子结点(结点指针,0
)入栈。 - 直到栈为空遍历结束。
时间复杂度
- 每个结点均摊遍历常数次,故时间复杂度也为 $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> preorder(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 == 0)
ans.push_back(cur.first -> val);
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));
}
}
return ans;
}
};