[数据结构与算法]二叉树遍历（非递归）

先序遍历

思想：当前节点不为空或栈不为空：树的值用vector记录，左子树边入栈边访问，直到判断当前节点为空为止。出栈，转向当前右子树。

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int>res;
        stack<TreeNode*>stack;
        if(root==nullptr) return res;
        
        TreeNode *cur=root;
        while(cur!=nullptr||!stack.empty()){
           while(cur!=nullptr){
                res.push_back(cur->val);
                stack.push(cur);
                cur=cur->left;
            }
            cur=stack.top();
            stack.pop();
            cur=cur->right;
        }
        return res;
        }
};

中序遍历

思想：当前节点不为空或栈不为空：左子树一直入栈，直到节点为空为止，此时先从栈中弹出节点，再访问节点值，转向当前右子树。

与先序区别：访问节点时机不同，先序边访问边入栈，中序左子树先入栈，出栈访问。

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int>res;
        stack<TreeNode*>stack;
        if(root==nullptr) return res;
        
        TreeNode *cur=root;
        while(cur!=nullptr||!stack.empty()){
           while(cur!=nullptr){
                stack.push(cur);
                cur=cur->left;
            }
            cur=stack.top();
            res.push_back(cur->val);
            stack.pop();
            cur=cur->right;
        }
        return res;
        }
};