二叉树前序中序后序遍历非递归写法

三种遍历的大体流程是不一样的，主要的区别在于控制何时visit。

中序遍历:

vector<int> inorderTraversal(TreeNode* root) {
    if(!root) return {};
    vector<int> ans;
    stack<TreeNode*> s;
    TreeNode *curr = root;
    while(curr || !s.empty()) {
        // Reach the left deep
        while(curr) {
            s.push(curr);
            curr = curr->left;
        }
        // Backtrack from the empty subtree and visit the node at the top of the stack; 
        // however, if the stack is empty you are done
        curr = s.top(); s.pop();
        ans.push_back(curr->val); // visit
        // We have visited the node and its left subtree. Now, its right subtree's turn
        curr = curr->right;
    }
    return ans;
}

前序遍历：

vector<int> preorderTraversal(TreeNode* root) {
    if(!root) return {};
    vector<int> ans;
    stack<TreeNode*> s;
    TreeNode *curr = root;
    while(curr || !s.empty()) {
        // Reach the left deep
        while(curr) {
            ans.push_back(curr->val); // visit
            s.push(curr);
            curr = curr->left;
        }
        // Backtrack from the empty subtree and visit the node at the top of the stack; 
        // however, if the stack is empty you are done
        curr = s.top(); s.pop();
        // We have visited the node and its left subtree. Now, its right subtree's turn
        curr = curr->right;
    }
    return ans;
}

与中序的差别仅仅是访问的时机改到了Reach the left deep循环中，让左子树入栈前就可以先访问当前节点了。

后序遍历：

vector<int> postorderTraversal(TreeNode* root) {
    if(!root) return {};
    vector<int> ans;
    stack<TreeNode*> s;
    TreeNode *curr = root;
    TreeNode *lastvisited = nullptr;
    while(curr || !s.empty()) {
        // Reach the left deep
        while(curr) {
            s.push(curr);
            curr = curr->left;
        }
        // Backtrack from the empty subtree and visit the node at the top of the stack; 
        // however, if the stack is empty you are done
        curr = s.top(); // 不能在这弹出，要等到访问完右子树第二次经过父节点

        if(!curr->right || lastvisited == curr->right) {
            // 刚刚已经访问过右子树（根据lastvisited标记）或者没有右子树（所以没法产生lastvisited标记），现在访问当前节点（这是第二次经过）
            ans.push_back(curr->val);
            s.pop();
            lastvisited = curr;
            curr = nullptr; //  置为空，以便继续弹出父节点
        } else {
            // 右子树还没访问过，转向右子树
            curr = curr->right;
        }
    }
    return ans;
}

主要区别在于，由于是需要全部子树访问完再，所以对于同一个节点会经过两次，
第一次经过只是取出其右子树，
第二次从其右子树返回到当前节点才是应该访问的时机，

我们需要借助lastvisited判断当前是否是从其右子树返回的第二次经过，并在此时visit和pop。

不要忘记更新lastvisited，以当该结点是右孩子时协助其父节点更新，
不要忘记curr置空

Donate