【C++】二叉树的遍历（前中后）- 迭代法-蒲公英云

【C++】二叉树的遍历（前中后）- 迭代法

Myth丶恋晨 2023-02-24 03:44 57阅读 0赞

力扣题目：https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

今天自己琢磨了很久如何不用递归将二叉树的遍历写出来，于是乎写出了如下代码。
优点：前中后序均只需要改一行代码的顺序；树的结构不会被破坏。

用栈显式的实现遍历，栈中元素为pair结构体，first是TreeNode*，second是int整形作为一个标记，0表示该树结点未被拓展（访问）过，1表示已经拓展过了。
思路（这里针对中序遍历）是栈中存放元素，如果第一次访问某个结点，将该结点出栈，然后若其右子结点非空，则入栈，然后该结点的标记位记为1然后再入栈，之后左子结点非空则入栈（前序和后序也只是在这里有区别）。之后什么时候输出呢，就是栈顶元素的标记位为1时输出：若为中间结点，这表示该结点已经拓展过了，不能再拓展了，若为叶子结点，则是拓展该结点是还是只有其本身进栈了。
处理一个结点时的顺序是右子结点进栈再左子结点进栈，而这个其本身进展的位置就决定了这是前序还是中序后序遍历。
Talk is cheap. show me the code.

class Solution { 
public:
    vector<int> inorderTraversal(TreeNode* root) { 
        vector<int> answer;
        stack<pair<TreeNode*,int>> data;
        if(root == NULL) return answer;
        data.push({ root,0});
        while(!data.empty()){ 
            auto top = data.top();
            data.pop();
            TreeNode* tem = top.first;
            int yesNode = top.second;
            if(yesNode == 1){ 
                answer.push_back(tem->val);
            }
            else{ 
                if(tem->right != NULL) data.push({ tem->right,0});
                data.push({ tem,1});
                if(tem->left != NULL) data.push({ tem->left,0});
            }
        }
        return answer;
    }
};