二叉树的遍历（非递归）

三种遍历：

• 先序：根   左  右
• 中序：左  根  右
• 后续：左   右  根

先看一种我认为比较秒的方法

vector<int> postorderTraversal(TreeNode* root) {
        if(root == NULL)  return vector<int>{};
        vector<int>res;
        stack<TreeNode*>st;
        st.push(root);
        while(!st.empty())
        {
            TreeNode* p = st.top();st.pop();
            res.push_back(p->val);
            if(p->left)  st.push(p->left);     // 先左
            if(p->right)  st.push(p->right);  // 后右，这样弹出时才能先右后左
        }
         reverse(res.begin(), res.end());
        return res;
    }

如果是先序遍历，只需改成先右后左；

但是这种方法不能实现中序遍历。

另外的思路是对访问过的节点进行标记，可以只标记最后一个被pop的

1、使用一个栈，先把二叉树的右孩子压入，再把左孩子压入。这样在输出时就满足后序要求（先左后右）。

2、当某个节点的左孩子或者右孩子都为NULL时，可以访问。此外记录当前节点p的上一个节点last，因为当p的左右孩子都已访问过时，轮到p被访问，设置last可标志p的左右孩子是否都被访问过了。即为 if((p->right == NULL && p->left == last) || p->right == last) 

vector<int> postorderTraversal(TreeNode* root) {
        if(root == NULL)  return vector<int>{};
        vector<int>res;
        stack<TreeNode*>st;
        st.push(root);
        TreeNode* pre;  // 记录上一个pop的节点
        while(!st.empty())
        {
            TreeNode* p = st.top();
            if((p->left == NULL && p->right == NULL) || (p->left == pre && p->right == NULL) || (p->right == pre))
            {
                res.push_back(p->val);
                pre = p;
                st.pop();
            }
            else
            {
                if(p->right)  st.push(p->right);
                if(p->left)  st.push(p->left);
            } 
        }
        return res;
    }

或者用unordered_map进行标记，

一种统一的写法：

二叉树的遍历都可以借助栈结构使用DFS算法完成。

首先是最简单的先序遍历，父>左>右。见144题 。
每次入栈前先将父节点加入结果列表，然后左节点入栈。
当左子树遍历完后，再遍历右子树。

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        res = []  #结果列表
        stack = []  #辅助栈
        cur = root  #当前节点
        while stack or cur:
            while cur:  #遍历到最后一层
                res.append(cur.val)  
                stack.append(cur)
                cur = cur.left
            top = stack.pop()  #此时该节点的左子树已经全部遍历完
            cur = top.right  #对右子树遍历
        return res

接着来看后序遍历，左>右>父。见145题 。
能不能借助先序遍历的思路来呢，我们将上面的顺序翻转过来得到，父>右>左。
所以现在可以按照之前的方法遍历，最后把结果翻转一下。

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        stack = []
        cur = root
        while stack or cur:
            while cur:
                res.append(cur.val)
                stack.append(cur)
                cur = cur.right  #先将右节点压栈
            top = stack.pop()  #此时该节点的右子树已经全部遍历完
            cur = top.left  #对左子树遍历
        return res[::-1]  #结果翻转

最后来看下中序遍历， 左>父>右。见94题 。
与先序遍历不同的是，出栈时才将结果写入列表。

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        stack = []
        cur = root
        while stack or cur:
            while cur:
                stack.append(cur)
                cur = cur.left
            top = stack.pop() #此时左子树遍历完成
            res.append(top.val)  #将父节点加入列表
            cur = top.right #遍历右子树
        return res

Morris遍历，一些线性时间复杂度，常数空间的算法，也可以实现三种遍历

对于1，2，3，4，5，6，7顺序组成的二叉树，cur依次遍历的是1 2 4 2 5 1 3 6 3 7

参考各自下方的官方题解

vector<int> inorderTraversal2(TreeNode* root) {
        vector<int>res;
        TreeNode* pre = nullptr, *cur = root;
        while(cur) {
            // cout << cur->val << " ";
            // if(cur->left)  cout << cur->left->val << " ";
            // if(cur->right) cout << cur->right->val << " ";
            // cout << endl;
            if(cur->left == nullptr) {
                // cout << "left: " <<  cur->val << endl;
                res.push_back(cur->val);
                cur = cur->right;
            } else {
                pre = cur->left; // pre 节点就是当前 root 节点向左走一步，然后一直向右走至无法走为止
                while(pre->right != nullptr && pre->right != cur) {
                    pre = pre->right;
                }

                if(pre->right == nullptr) {
                    pre->right = cur;
                    cur = cur->left;
                } else {
                    pre->right = nullptr;  // 断开连接
                    // cout << "after: " << cur->val << endl; // 中间节点
                    res.push_back(cur->val);
                    cur = cur->right;
                }
            }
        }
        return res;
    }

    vector<int> preorderTraversal2(TreeNode* root) {
        vector<int> res;
        TreeNode* cur = root, *pre = NULL;
        while(cur) {
            if(cur->left == NULL) {  // 回到中
                res.push_back(cur->val);
                cur = cur->right;
            }
            else {
                
                pre = cur->left;
                while(pre->right != NULL && pre->right != cur) {
                    pre = pre->right;
                }
                if(pre->right == NULL) { // 先
                    res.push_back(cur->val);
                    pre->right = cur;
                    cur = cur->left;
                }
                else {  // 后
                    pre->right = NULL;
                    cur = cur->right;
                }
            }
        }
        return res;
    }  

前面两个没啥区别，只是添加答案的位置不同
后续遍历有点不好看懂...

    void addPath(vector<int>& vec, TreeNode* node) {
        int cnt = 0;
        while(node) {
            vec.push_back(node->val);
            node = node->right;
            cnt++;
        }
        reverse(vec.end()-cnt, vec.end());
    }
    vector<int> postorderTraversal2(TreeNode* root) {
        vector<int> res;
        TreeNode* cur = root, *pre = NULL;
        while(cur) {
            if(cur->left == nullptr) {
                // pre = cur->left;
            } else  {
                pre = cur->left;
                while(pre->right != NULL && pre->right != cur) {
                    pre = pre->right;
                }
                if(pre->right == NULL) { // 先
                    // res.push_back(cur->val);
                    pre->right = cur;
                    cur = cur->left;
                    continue;
                }
                else {  // 后
                    pre->right = NULL;
                    addPath(res, cur->left);
                }
            }
            cur = cur->right;
        }
        addPath(res, root);
        return res;
    }   

参考链接：

1. https://blog.csdn.net/exceptional_derek/article/details/17551459

2. https://www.cnblogs.com/moxiangfeng/p/10738591.html

3. https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/liang-ta-lai-liao-ta-dai-zhao-san-xiong-di-lai-lia/