二叉树的Morris遍历

二叉树的Morris遍历，$O(1)$空间，非递归

概述 §

二叉树的Morris遍历是一种非递归遍历算法，且仅使用$O(1)$的额外空间

算法保证在结束时树的结构不被修改，但需要在算法过程中临时添加回边，因此适用于可以修改的树

具体来说，算法需要拥有节点的右儿子指针Left: Node*的修改权限

传统的中序遍历 §

递归 §

递归形式好写，但缺点是递归调用比较耗时

1| void inorder(Node* root) {
2|     if(root->left) inorder(root->left);
3|     visit(root);
4|     if(root->right) inorder(root->right);
5| }

遍历过程中调用栈的最大深度为树的高度，在平衡树中为$O(\log n)$，最坏情况为$O(n)$

非递归 §

01| void inorder(Node *root) {
02|     stack<Node *> S;
03|     TreeNode *ptr = root;
04|     while (ptr || !S.empty()) {
05|         while (ptr) {
06|             S.push(ptr);
07|             ptr = ptr->left;
08|         }
09|         ptr = S.top(); S.pop();
10|         visit(ptr);
11|         ptr = ptr->right;
12|     }
13| }

算法从当前指针ptr出发，一路沿着left走到子树的最左边，并沿途保存所有节点到栈中（05-08），此时栈S中除了栈顶为leftmost的节点，其余的均为局部视角的根节点

(09-10)访问leftmost的节点，此后进入右子树进行遍历(11+后续)

每个节点访问一次，时间复杂度$O(n)$

栈深度同上，在平衡树中为$O(\log n)$，最坏情况为$O(n)$

Morris中序遍历 §

首先思考上面的非递归法为什么要使用栈，这是因为我们在访问完左子树后需要访问根，然后访问右子树，如果不做相应保存，那就回不去到根节点了

再重新思考一下中序遍历的过程：

1. 访问左子树
2. 访问根节点
3. 访问右子树

其中步骤1的结束标志为访问到了其rightmost，也就是最右边的节点，此后便回到根节点

注意到最右边的节点肯定是没有右儿子的，如果我们能利用这个右儿子指针，让它指向理应跳回的根节点，这样我们就能不借助额外的容器空间完成遍历了

因此对于每个节点A，我们执行以下几步

1. 如果它有左子树，那么现在进入它的右子树找到最右边的节点B

   情况A：如果节点B的右儿子为空，就把这个指针指向节点A（这就是一个临时邻接），然后进入步骤2

   情况B：如果节点B的右儿子为节点A，则断开这个临时链接，进入步骤3

2. 如果它没有左子树，则进入步骤4

3. 进入节点A的左子树

4. 访问根节点A，然后进入节点A的右子树

举个🌰 §

对于一棵树

从节点1开始，查看左子树，首先找到最右边的节点5，连回当前节点1

之后进入左儿子2，同理查看左子树，无法继续向右走，因此4连回2

之后进入左儿子4，由于没有左子树，则直接输出当前节点4，之后进入右子树，即沿着之前建立的临时链接跳回节点2

回到2但是依旧执行之前的步骤，进入左儿子4寻找rightmost的节点，走完后发现这个节点（也就是左儿子4）的右儿子节点不为空，这说明这是第二次访问左子树的rightmost节点，我们就断开这个临时链接，输出当前节点2，之后跳入右子树

同理，节点5没有左儿子，于是直接输出当前的值5，并进入右子树，也就是跳回节点1

节点1有左子树，于是寻找rightmost节点，找到了节点但是发现它不为空，断开连接，输出当前节点1，之后跳入右子树

进入节点3，没有左儿子，于是直接输出节点值3，然后前往右子树

但右子树为空，过程结束

输出：4 2 5 1 3

以上便是Morris中序遍历的简单举例

C++代码 §

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    explicit TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

void inorder(TreeNode *root, const function<void(TreeNode *)> &helper) {
    /**
     * Morris 中序遍历
     *   1. 非递归实现
     *   2. 常数的临时空间
     */
    if (root == nullptr)
        return;

    TreeNode *current, *rightmost;

    current = root;
    while (current != nullptr) {
        if (current->left == nullptr) {
            /**
             * 没有左孩子，直接输出当前的值并前往右子树
             */
            helper(current);
            current = current->right;
        } else {
            /**
             * 有左子树，开始寻找左子树中最右边的节点
             */
            rightmost = current->left;
            while (rightmost->right != nullptr && rightmost->right != current) {
                rightmost = rightmost->right;
            }

            /**
             * 此时rightmost存储的便是current的左子树中，rightmost的节点
             */

            if (rightmost->right == nullptr) {
                /**
                 * rightmost的节点的右孩子为空，
                 * 说明这是第一次访问这个节点，
                 * 建立回跳连接，返回current
                 * >>>这个临时链接会在下个else删除<<<
                 */
                rightmost->right = current;
                current = current->left;
            } else {
                /**
                 * 明明是rightmost的节点却有右孩子，
                 * 说明这是第二次访问这个rightmost的节点，
                 * 这意味着进行到了中序遍历中的根节点阶段（{左}-[根]-{右}），
                 * 断开之前建立的临时连接，输出（子）树根，然后跳入右子树
                 */
                rightmost->right = nullptr; // 恢复原有状态
                helper(current);
                current = current->right;
            }
        }
    }
}

TreeNode *makeNode(int val) { return new TreeNode(val); }

int main() {
    auto root = makeNode(1);
    root->left = makeNode(2);
    root->right = makeNode(3);
    root->left->left = makeNode(4);
    root->left->right = makeNode(5);
    inorder(root, [](TreeNode *node) { cout << node->val << " "; });
    return 0;
}

复杂度分析 §

两个指针，因此空间复杂度为$O(1)$

每条边最多走两次，第一次为了找到对应节点，而当这个节点处于某个右子树路径时，还会有第二次访问，是为了找到节点后删除临时链接，因此时间复杂度仍为$O(n)$，不过常数较大