An Iterative 3-in-1 Template for Pre/In/Post-order Traversal
Explanation\n\nOne only needs to write the code to the corresponding block.\n\nThe concept is exactly how recursion works.\nWe:\n\n- only traverse while the sta
## Explanation\n\nOne only needs to write the code to the corresponding block.\n\nThe concept is exactly how recursion works.\nWe:\n\n- only traverse while the stack is not empty.  (#0)\n- push a left child to the stack right after a pre-order region.  (#3)\n- push a right child to the stack right after an in-order region.  (#6)\n- pop the stack right after a post-order region.  (#8)\n\nAnd there are some implementation details:\n\n-  If a traversal is not a in-order nor post-order traversal, it\'s a pre-order traversal. (#1)\n-  Use a `while (true)` with a `if` statement inside to ensure `node` is not null outside the loop.  (#2, #4)\n-  If a node has no right child, the in-order operation and post-order operation happen simutaneously. (#5, #7)\n-  `prev` is the last post-order traversed node. (#9)\n\n## Template\n\n```C++\n        stack<TreeNode*> stack{};\n        TreeNode* prev = nullptr;\n\n        if (root)\n            stack.push(root);\n        while (not stack.empty()) {  // #0\n            TreeNode* node = stack.top();\n\n            if (not prev or\n                prev != node->left and prev != node->right) {  // #1\n                while (true) {\n                    // Pre-order region {\n                    //   do_something();\n                    // }\n                    if (not node->left)\n                        break;   // #2\n                    node = node->left;\n                    stack.push(node);  // #3\n                }\n            }\n            // #4\n            if (not node->right or prev != node->right) {  // #5\n                // In-order region {\n                //   do_something();\n                // }\n                if (node->right)\n                    stack.push(node->right);  // #6\n            }\n\n            if (not node->right or prev == node->right) {  // #7\n                // Post-order region {\n                //   do_something();\n                // }\n                stack.pop();  // #8\n                prev = node;  // #9\n            }\n        }\n```\n\n## A slightly changed version\n\n```C++\n        stack<TreeNode*> stack{};\n        TreeNode* node = root;\n        TreeNode* prev = nullptr;\n\n        while (node or not stack.empty()) {\n            while (node) {\n                // Pre-order region {\n                //   do_something();\n                // }\n                stack.push(node);\n                node = node->left;\n            }\n            node = stack.top();\n\n            if (not node->right or prev != node->right) {\n                // In-order region {\n                //   do_something();\n                // }\n                if (node->right) {\n                    node = node->right;\n                    continue;\n                }\n            }\n\n            if (not node->right or prev == node->right) {\n                // Post-order region {\n                //   do_something();\n                // }\n                stack.pop();\n                prev = node;\n                node = nullptr;\n            }\n        }\n```\n\n## Examples\n\n### [Problem: Binary Tree Preorder Traversal](https://leetcode.com/problems/binary-tree-preorder-traversal/)\n\n```C++\nclass Solution {\npublic:\n    vector<int> preorderTraversal(TreeNode* root) {\n        vector<int> result{};\n        stack<TreeNode*> stack{};\n        TreeNode* prev = nullptr;\n\n        if (root)\n            stack.push(root);\n        while (not stack.empty()) {\n            TreeNode* node = stack.top();\n\n            if (not prev or\n                prev != node->left and prev != node->right) {\n                while (true) {\n                    // Pre-order region {\n                    result.push_back(node->val);  // <-------------- See here!\n                    // }\n                    if (not node->left)\n                        break;\n                    node = node->left;\n                    stack.push(node);\n                }\n            }\n\n            if (not node->right or prev != node->right) {\n                // In-order region {\n                //   do_something();\n                // }\n                if (node->right)\n                    stack.push(node->right);\n            }\n\n            if (not node->right or prev == node->right) {\n                // Post-order region {\n                //   do_something();\n                // }\n                stack.pop();\n                prev = node;\n            }\n        }\n        return result;\n    }\n};\n```\n\n### [Problem: Binary Tree Inorder Traversal](https://leetcode.com/problems/binary-tree-inorder-traversal/)\n\n```C++\nclass Solution {\npublic:\n    vector<int> inorderTraversal(TreeNode* root) {\n        vector<int> result{};\n        stack<TreeNode*> stack{};\n        TreeNode* prev = nullptr;\n\n        if (root)\n            stack.push(root);\n        while (not stack.empty()) {\n            TreeNode* node = stack.top();\n\n            if (not prev or\n                prev != node->left and prev != node->right) {\n                while (true) {\n                    // Pre-order region {\n                    //   do_something();\n                    // }\n                    if (not node->left)\n                        break;\n                    node = node->left;\n                    stack.push(node);\n                }\n            }\n\n            if (not node->right or prev != node->right) {\n                // In-order region {\n                result.push_back(node->val);  // <-------------- See here!\n                // }\n                if (node->right)\n                    stack.push(node->right);\n            }\n\n            if (not node->right or prev == node->right) {\n                // Post-order region {\n                //   do_something();\n                // }\n                stack.pop();\n                prev = node;\n            }\n        }\n        return result;\n    }\n};\n```\n\n### [Problem: Binary Tree Postorder Traversal](https://leetcode.com/problems/binary-tree-postorder-traversal/)\n\n```C++\nclass Solution {\npublic:\n    vector<int> postorderTraversal(TreeNode* root) {\n        vector<int> result{};\n        stack<TreeNode*> stack{};\n        TreeNode* prev = nullptr;\n\n        if (root)\n            stack.push(root);\n        while (not stack.empty()) {\n            TreeNode* node = stack.top();\n\n            if (not prev or\n                prev != node->left and prev != node->right) {\n                while (true) {\n                    // Pre-order region {\n                    //   do_something();\n                    // }\n                    if (not node->left)\n                        break;\n                    node = node->left;\n                    stack.push(node);\n                }\n            }\n\n            if (not node->right or prev != node->right) {\n                // In-order region {\n                //   do_something();\n                // }\n                if (node->right)\n                    stack.push(node->right);\n            }\n\n            if (not node->right or prev == node->right) {\n                // Post-order region {\n                result.push_back(node->val);  // <-------------- See here!\n                // }\n                stack.pop();\n                prev = node;\n            }\n        }\n        return result;\n    }\n};\n```
['Stack', 'Iterator', 'C++']