<Data Structures/Algorithms> leetcode hot100 - 94.Binary Tree Inorder Traversal (with non-recursive pre/in/postorder traversal)

[LeetCode Hot 100] 94. Binary Tree Inorder Traversal

Problem Link

Inorder Traversal (Non-Recursive)

Inorder traversal follows the order: left subtree → root → right subtree. To implement it non-recursively, we use a stack to save root nodes. After finishing the left subtree, pop the root from the stack and then traverse the right subtree.

The main idea:

• Use a pointer cur to track the current node, instead of relying on the stack top.
• While cur exists, push it to the stack and move to cur->left.
• When cur becomes null, pop from the stack, visit the node, and move to its right child.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> ans;
        TreeNode* cur = root;
        while(cur || !st.empty()){
            while(cur){
                st.push(cur);
                cur = cur->left;
            }
            cur = st.top();
            st.pop();
            ans.push_back(cur->val);
            cur = cur->right;
        }
        return ans;
    }
};

Preorder Traversal (Non-Recursive)

Preorder traversal is simpler since we just need to push the right child first, then the left child. Each iteration, the top of the stack is the current node.

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

Postorder Traversal (Non-Recursive)

Key: track the last visited node prev. A node can only be visited when:

• It has no children, or
• Its children have already been visited.

Otherwise, push its right and left children to the stack.

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

Postorder Using Modified Preorder

Preorder traversal with left and right swapped gives a sequence that is the reverse of postorder. After performing modified preorder, reverse the result to get postorder.

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> ans;
        if(!root) return ans;
        st.push(root);
        while(!st.empty()){
            TreeNode* cur = st.top();
            st.pop();
            ans.push_back(cur->val);
            if(cur->left) st.push(cur->left);
            if(cur->right) st.push(cur->right);
        }
        reverse(ans.begin(), ans.end()); // reverse to get postorder
        return ans;
    }
};

中文原文

[LeetCode hot 100] 94. 二叉树中序遍历

题目链接

这里我们主要说非递归。

由于中序遍历是左子树-根-右子树的顺序，因此我们在设计算法的时候需要使用栈保存根节点，当左子树遍历完了，再将根节点出栈，然后访问右子树。

我们直观的想法就是：首先把根节点进栈，然后左孩子进栈，直到把左子树处理完了之后把根节点露出来，然后输出根节点，根节点出栈，根节点的右孩子入栈。这玩意咋用循环迭代实现呢？把根节点拿出来访问右子树这个都会，问题是左子树入栈该遵循一个什么原则呢？理论上我们每次循环判断当前节点如果有左子树就入栈不就行了？

但是有个问题就是我们不能在出栈的时候再判断有没有左孩子，也就是说找左孩子的活不能从栈顶拿元素再判断，那样的话如果发现有左孩子，你的根节点（也就是现在的栈顶）就不能出栈，但是你最后左子树搞了一圈之后就会发现，栈顶又变成这个根节点了，由于每次循环的判定逻辑都是一样的，所以它的左孩子又会入栈，就成了死循环。

因此，需要有一个指针来记录当前遍历到的节点，而不是依靠栈顶元素，不然乱套了。每次当前节点有左孩子，就先将当前节点入栈，然后将指针指向左孩子，此时将当前节点入栈的操作代表“我记住你了，待会儿再来遍历你和你的右子树”。不断地将指针指向左孩子，其实就是不断记忆的过程，因为一旦一个节点有左孩子，就要优先处理左子树，先记住根节点和右子树，过后再说。

直到我们遇到了null，说明终于没有更下一层的左子树了，该遍历中间节点和右子树了，而中间节点现在就在栈顶，这不就好办了吗？

代码如下，实在理解不了咱就直接背下来吧，别折磨自己了，这博客我写了一小时还没法用流畅的语言表达出来，真吐了。怪不得程序员当久了语言功能会退化。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> ans;
        TreeNode* cur = root;
        while(cur || !st.empty()){
            while(cur){
                st.push(cur);
                cur = cur->left;
            }
            cur = st.top();
            st.pop();
            ans.push_back(cur->val);
            cur = cur->right;
        }
        return ans;
    }
};

前序遍历非递归

那顺便来说一下前序遍历的非递归实现。这个就简单很多，因为不用保存根节点，省去了很多麻烦事，直接把右孩子和左孩子先后入栈即可，每次循环，栈顶元素就是当前节点

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

后序遍历非递归

后序遍历的关键之关键之关键是要保存一下上一次访问的节点，因为虽然先访问的是根节点，但是根节点却不能出栈。为了在访问栈顶结点的时候方便判断是左子树右子树都遍历完了还是都没有遍历，需要保存上一个访问的节点，如果上一个访问的是左孩子或右孩子，那就说明需要访问根节点并且出栈，否则就说明需要将左右孩子入栈。

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

事实上还有一种更讨巧的算法，那就是前序遍历只要把左右子树的顺序换一下，就刚好与后序遍历的序列相反。因此可以用前序遍历来构造后序遍历。

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> ans;
        st.push(root);
        while(!st.empty()){
            TreeNode* cur = st.top();
            ans.push_back(cur->val);
            if(cur->left){
                st.push(cur->left);
            }
            if(cur->right){
                st.push(cur->right);
            }
        }
        reverse(ans.begin(), ans.end());	//反转后就是后续遍历的序列
        return ans;
    }
};