# Morris 遍历

## 6/3, Tree, Morris 遍历

## [这个帖子](http://blog.codinghonor.com/2014/11/26/morris-traversal/) 的描述和代码非常好，还有[这个](http://www.cnblogs.com/AnnieKim/archive/2013/06/15/MorrisTraversal.html)。

我一开始以为 Morris 遍历会改变原树的结构所以不能用，后来发现并不会。。。于是这种技巧还是很值得掌握的。

1968年，Knuth提出说能否将该问题的空间复杂度压缩到O(1)，同时原树的结构不能改变。大约十年后，1979年，Morris在《Traversing Binary Trees Simply and Cheaply》这篇论文中用一种Threaded Binary Tree的方法解决了该问题。

## 每次访问root左子树之前，先找到左子树里面最右面的点，并把其 right 指针连到 root 上；左子树遍历完这个点之后，再把这个多出来的指针拆掉。

## Morris in-order 流程，利用 threaded binary tree.

![](/files/-MUt7_Ipt67MUV4tszkO)

```java
public class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        TreeNode cur = root;
        while(cur != null){
            if(cur.left == null){
                list.add(cur.val);
                cur = cur.right;
            } else {
                TreeNode prev = cur.left;
                while(prev.right != null && prev.right != cur){
                    prev = prev.right;
                }
                if(prev.right == null){
                    prev.right = cur;
                    // Uncomment for pre-order
                    // list.add(cur.val);
                    cur = cur.left;
                } else {
                    prev.right = null;
                    // Uncomment for in-order
                    // list.add(cur.val);
                    cur = cur.right;
                }
            }
        }
        return list;
    }
}
```

## 于是这道要求用 O(n) 时间 O(1) 空间的题就可以真正按照题目要求解决了。

## [Recover Binary Search Tree](https://leetcode.com/problems/recover-binary-search-tree/)

```java
public class Solution {
    public void recoverTree(TreeNode root) {
        TreeNode cur = root;
        TreeNode prevNode = null;
        TreeNode p = null;
        TreeNode q = null;

        while(cur != null){
            if(cur.left == null){
                if(prevNode != null && prevNode.val >= cur.val){
                    if(p == null) p = prevNode;
                    q = cur;
                }
                // Set prev node for scanning
                prevNode = cur;
                cur = cur.right;
            } else {
                TreeNode prev = cur.left;
                while(prev.right != null && prev.right != cur){
                    prev = prev.right;
                }
                if(prev.right == null){
                    prev.right = cur;
                    cur = cur.left;
                } else {
                    prev.right = null;

                    if(prevNode != null && prevNode.val >= cur.val){
                        if(p == null) p = prevNode;
                        q = cur;
                    }
                    // Set prev node for scanning
                    prevNode = cur;
                    cur = cur.right;
                }
            }
        }

        swap(p, q);
    }

    private void swap(TreeNode p, TreeNode q){
        if(p == null || q == null) return;
        int temp = p.val;
        p.val = q.val;
        q.val = temp;
    }
}
```

## Morris 的 post-order 遍历还要建一个 dummy node 以及反序输出。。感觉不是非常现实。。。有空复习的时候我再研究研究这种 trick 吧。

![](/files/-MUt7_IruPbjkClWd9XA)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mnunknown.gitbook.io/algorithm-notes/binary_tree/63-_tree-_morris_bian_li.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.