【每天学点算法系列】morris遍历

二叉树的遍历通常O(n)的时间复杂度与O(logn)的空间复杂度，而morris遍历实现了O(n)的时间复杂度和O(1)的空间复杂度…

morris遍历的原理

对于没有左子树的节点只达到一次，对于有左子树的节点会到达两次；

morris遍历的实现原则

记当前节点为cur

如果cur无左子树，cur右移（cur = cur.right）;
如果cur有左子树，找到cur左子树最右的节点，记做mostright；
- 如果mostright的right指针为空，则将其指向cur（mostright.right = cur），cur左移（cur = cur.left）;
- 如果mostright的right指针指向cur，则将其置为空（mostright.right = null），cur右移（cur = cur.right）;

图示：

show

代码实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        //当前节点和前驱节点
        TreeNode cur = root;
        TreeNode pre = null;

        //当cur不为null的时候
        while (cur != null) {
            //如果当前节点没有左儿子，就走右儿子
            if (cur.left == null) {
                list.add(cur.val);
                cur = cur.right;
            } else {
                //当前节点有左儿子，那么就要找到当前节点的前驱，就是从它的左儿子，然后一直往右走到底。且 不为当前cur节点
                pre = cur.left;
                while (pre.right != null && pre.right != cur) {
                    pre = pre.right;
                }
                // 如果前驱节点的右节点已经被设置，也就是我们设置过线索了，需要将它右孩子重新设置为空，输出当前节点。
                // cur更新为cur.right，因为因为我们走的是cur.left，如果设置过线索，就说明左边都访问过了，要看右边
                if (pre.right == cur) {
                    list.add(cur.val);
                    pre.right = null;
                    cur = cur.right;
                } else {
                    //如果是第一次访问该节点，也就是还没有设置线索，要设置线索，它的right即为当前节点，然后我们继续看cur.left，因为左边还没设置
                    pre.right = cur;
                    cur = cur.left;
                }

            }
        }
        return list;
    }
}

补充思考

1、为什么morris遍历的空间复杂度为O(1)，而一遍的遍历为O(logN)呢？怎么计算的？

一般二叉树的遍历：

先序遍历：按照 父节点 -> 左孩子 -> 右孩子 的顺序遍历，与DFS（深度优先搜索）有一定联系；

中序遍历：按照 左孩子 -> 父节点 -> 右孩子 的顺序遍历。当二叉树为二叉搜索树时，中序遍历返回结果为有序序列，因此也叫顺序遍历；

后序遍历：按照 左孩子 -> 右孩子 -> 父节点 的顺序遍历。

层次遍历：从左到右，一层一层遍历整个树，与BFS（广度优先搜索）有一定联系。

比如我们用栈来完成一个二叉树的先序遍历，通常是这样：

public void preOrderTraversal(TreeNode root) {
	if (root == null) return;
	Stack<TreeNode> stack = new Stack<TreeNode>(); // 利用栈进行临时存储
	stack.push(root);

	while (!stack.isEmpty()) {
		TreeNode node = stack.pop(); // 取出一个节点，表示开始访问以该节点为根的子树
		visit(node); // 首先访问该节点（先序），之后顺序入栈右子树、左子树
		if (node.right != null) stack.push(node.right);
		if (node.left != null) stack.push(node.left);
	}
}