Given a binary tree, return the preorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3},
1
\
2
/
3
return [1,2,3].
Note: Recursive solution is trivial, could you do it iteratively?
使用迭代(非递归)的方法遍历二叉树。
可以使用stack或者list记录遍历的回退路径，实现前序遍历。
class Solution {
public:
vector<int> preorderTraversal(TreeNode *root) {
vector<int> vec;
if(root==NULL)
return vec;
stack<TreeNode*> s;
s.push(root);
TreeNode *current;
while(!s.empty()){
current = s.top();
s.pop();
if(current){
vec.push_back(current->val);
s.push(current->right);
s.push(current->left);
}
}
return vec;
}
};
class Solution {
public:
vector<int> preorderTraversal(TreeNode *root) {
vector<int> vec;
if(root==NULL)
return vec;
list<TreeNode*> L;
L.push_back(root);
TreeNode *current;
while(!L.empty()){
current = L.front();
L.pop_front();
if(current){
vec.push_back(current->val);
L.push_front(current->right);
L.push_front(current->left);
}
}
return vec;
}
};
两者的时间复杂度均是O(n)，额外的stack或者list的空间复杂度都是O(logn)，但list内部需要维护结点之间的链接指针，所以stack的实际运行效率要更好一些。
