最简单的就是前序遍历,每次将栈顶元素插入数组中。
但要注意由于栈的性质,先push右节点再push左节点。
点击查看代码
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int>v;
stack<TreeNode*>stk;
if(root!=NULL){stk.push(root);}
while(!stk.empty()){
TreeNode*p=stk.top();
v.push_back(p->val);
stk.pop();
if(p->right){stk.push(p->right);}
if(p->left){stk.push(p->left);}
}
return v;
}
};
点击查看代码
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int>v;
stack<TreeNode*>stk;
TreeNode*p=root;
while(p!=NULL||!stk.empty()){
if(p!=NULL){
stk.push(p);
p=p->left;
}
else{
p=stk.top();
v.push_back(p->val);
stk.pop();
p=p->right;
}
}
return v;
}
};