迭代法遍历

利用栈实现二叉树的前中后序迭代遍历

// 前序
class Solution {
public:
    vector preorderTraversal(TreeNode* root) {
       stack stk;
       vector res;
       if(root==nullptr){
           return res;
       }
       TreeNode* cur=root;
       while(cur!=nullptr || !stk.empty()){
           while(cur){ //根节点和左孩子入栈
               res.push_back(cur->val);
               stk.push(cur);
               cur=cur->left;
           }
           TreeNode* tmp=stk.top(); // 每弹出一个元素，就到达右孩子
           stk.pop();
           cur=tmp->right;
       }
       return res;  
    }   
};

// 中序
class Solution{
    public:
    vector inorderTraversal(TreeNode* root){
       stack stk;
       vector res;
       if(root==nullptr){
           return res;
       }
       TreeNode* cur=root;
       while(cur!=nullptr || !stk.empty()){
           while(cur){ // 入栈，并到达最左端的叶子节点
               //res.push_back(cur->val);
               stk.push(cur);
               cur=cur->left;
           }
           TreeNode* tmp=stk.top(); // 每弹出一个元素，就到达右孩子
           res.push_back(tmp->val);  // 出栈时再加入结果
           stk.pop();
           cur=tmp->right;
       }
       return res;  
    } 
};

// 后序
class Solution {
public:
    vector postorderTraversal(TreeNode* root) {
       stack stk;
       vector res;
       if(root==nullptr){
           return res;
       }
       TreeNode* cur=root;
       while(cur!=nullptr || !stk.empty()){
           while(cur){ // 先到达最右端
               res.push_back(cur->val);
               stk.push(cur);
               cur=cur->right;
           }
           TreeNode* tmp=stk.top(); // 每弹出一个元素，就到达右孩子
           stk.pop();
           cur=tmp->left;
       }
       reverse(res.begin(),res.end()); //反向输出
       return res;  
    }   
};