Share my iterative solution with explanation


  • 0
    T

    The basic idea is to imitate the process of recursion. The key is to use a variable to record the latest visited node in order to avoid duplicates.

    At the beginning, the stack is empty and the current node is root. Then, the process goes as follow:

    1. keep going left util reaching the leftmost child.

    2. now the current node is the leftmost child, then check its right child. There are two cases:

      • empty or visited: visit current node, then return back to its parent, do step 2 again. don't forget to mark the visited node
      • unvisited: push the current node into the stack, then set the right child as the current node, break and go back to step 1 to process the right subtree.

    Source code:

        vector<int> postorderTraversal(TreeNode* root) {
            vector<int> res;
            if (!root) return res;
            vector<TreeNode *> stk;
            TreeNode * pre = NULL;//lastest visited node
            do {
                while (root) {//keep going left
                    stk.push_back(root);
                    root = root->left;
                }
                pre = NULL;
                while (!stk.empty()) {
                    root = stk.back();
                    stk.pop_back();
                    if (!root->right || root->right == pre) {//empty or visited
                        res.push_back(root->val);
                        pre = root;
                    }
                    else {//put root back to the stack and turn right
                        stk.push_back(root);
                        root = root->right;
                        break;
                    }
                }
            } while (!stk.empty());
            return res;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.