思想

• Morris遍历利用左右节点为空的空节点指针建立线索二叉树，将空闲的叶子节点指向上层的后继节点，保证右子树先于根被遍历到。实质是没有左子树的节点只会被访问一次，有左子树的节点会被访问两次，第一次访问建立向上走的线索，第二次访问清空之前建立的线索。

遍历过程

• 从根节点开始遍历，假设当前节点为$cur$：
  • 如果$cur$没有左孩子，则前往$cur$的右孩子（即cur = cur->right）
  • 如果$cur$有左孩子，则寻找左子树上的最右节点$pre$：
    • 如果$pre$的右孩子为空，则将其右指针指向$cur$，$cur$向左移动；
    • 如果$pre$的右孩子为$cur$，则将其右指针指向空，$cur$向右移动。
• 时间复杂度$O(n)$，空间复杂度$O(1)$（不算保存答案用的数组）。

具体代码如下

#include <iostream>
#include <vector>

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) {}
};

// 前序遍历
vector<int> preorderTraversal(TreeNode* root) {
    vector<int> res;
    if (root == nullptr) return res;
    TreeNode *pre, *cur;
    cur = root;
    while (cur) {
        if (cur->left == nullptr) {
            res.push_back(cur->val);
            cur = cur->right;
        } else {
            pre = cur->left;
            while (pre->right != nullptr && pre->right != cur) pre= pre->right;
            if (pre->right == nullptr) {
                // 和中序不同，第一次访问到cur的时候将其加入前序序列
                // 此时cur的左子树还未被遍历
                res.push_back(cur->val);
                pre->right = cur;
                cur = cur->left;
            } else {
                pre->right = nullptr;
                cur = cur->right;
            }
        }
    }
    return res;
}

// 中序遍历
vector<int> inorderTraversal(TreeNode* root) {
    vector<int> res;
    if (root == nullptr) return res;
    TreeNode *pre, *cur;
    cur = root;
    while (cur != nullptr) {
        // cur的左子节点为空，说明不存在左子树，将cur的值放入中序序列，然后cur指向右子节点
        if (cur->left == nullptr) {
            res.push_back(cur->val);
            cur = cur->right;
        } else {
            // 找到cur的左子树中的最右节点pre
            pre = cur->left;
            while (pre->right != nullptr && pre->right != cur) pre= pre->right;
            // 如果pre的右子节点为空，说明是第一次遍历到，将其指向cur
            // 之后cur指向其左子节点
            if (pre->right == nullptr) {
                pre->right = cur;
                cur = cur->left;
            } else {
            // 如果pre的右子节点指向cur，说明是第二次遍历到，将其指向空
            // 此时说明cur的左子树已经遍历完，将cur的值放入中序序列，然后cur指向右子节点
                pre->right = nullptr;
                res.push_back(cur->val);
                cur = cur->right;
            }
        }
    }
    return res;
}
// 后序遍历
// 前序遍历是 中-左-右，而后序遍历是 左-右-中，
// 如果将前序遍历的左右顺序交换，就得到了后序遍历的逆序 中-右-左
// 因此后序遍历就是将前序遍历中的左变成右，最后翻转res数组即可
vector<int> postorderTraversal(TreeNode* root) {
    vector<int> res;
    if (root == nullptr) return res;
    TreeNode *pre, *cur = root;
    while (cur != nullptr) {
        if (cur->right == nullptr) {
            res.push_back(cur->val);
            cur = cur->left;
        } else {
            pre = cur->right;
            while (pre->left != nullptr && pre->left != cur) pre = pre->left;
            if (pre->left == nullptr) {
                res.push_back(cur->val);
                pre->left = cur;
                cur = cur->right;
            } else {
                pre->left = nullptr;
                cur = cur->left;
            }
        }
    }
    reverse(res.begin(), res.end());
    return res;
}