[Algorithm]Binary Tree Morris Traversal

Binary Tree的Traversal问题总是面试的重点。不管是recursive还是iterative的版本，我们都需要额外的空间。

下面我们介绍一种只需要constant space的traversal的办法，Morris Traversal。

既然是constant space，那么难点就在于，当右子结点为空时，如何去找到后继节点。要解决这个问题，必须引入一个数据结构Threaded Binary Tree，在这里，我们把所有右子树为空的节点的右指针连接到它的后继节点。这样，当我们走到这些节点时，就可以直接去右子结点就找到了后继结点，当然要注意的问题是，我们这么做会破坏树的结构，所以遍历的时候还要注意恢复二叉树的原始结构。也正是由于这个原因，Morris Traversal不适用于二叉树的迭代器，如果迭代器用到了一半丢弃了，二叉树的结构就被破坏了。

1. Preorder Traversal

大体思路是，当前节点c如果没有左子树，加入结果集，然后去到右子结点。如果当前节点c有左子树，把c加入结果集，然后在c的左子树中找到c的前驱节点p并且把p的右指针指向c，去到c的左子结点。当再次通过p回到c的时候，把p的右节点重置，去到c的右子结点。直到到达最右侧的节点，右子结点为null，结束。

过程如下图所示(图片来自 Annie Kim's Blog)：

代码如下：

	/**
	* Definition for binary tree
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	public class Solution {
	public List<Integer> preorderTraversal(TreeNode root) {
	List<Integer> res = new ArrayList<Integer>();
	if (root == null)
	return res;
	TreeNode curr = root;
	while (curr != null) {
	if (curr.left == null) {
	res.add(curr.val);
	curr = curr.right;
	} else {
	TreeNode temp = curr.left;
	while (temp.right != null && temp.right != curr) {
	temp = temp.right;
	}
	if (temp.right == null) {
	temp.right = curr;
	res.add(curr.val);
	curr = curr.left;
	} else {
	temp.right = null;
	curr = curr.right;
	}
	}
	}
	return res;
	}
	}

view raw morris preorder.java hosted with ❤ by GitHub

2. Inorder Traversal

思路与Preorder是一样的，区别在于，我们在第二次访问节点，也就是说从p回到c的时候才把c加入结果集。

过程如下图所示(图片来自 Annie Kim's Blog)：

代码如下：

	/**
	* Definition for binary tree
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	public class Solution {
	public List<Integer> inorderTraversal(TreeNode root) {
	List<Integer> res = new ArrayList<Integer>();
	if (root == null)
	return res;
	TreeNode curr = root;
	while (curr != null) {
	if (curr.left == null) {
	res.add(curr.val);
	curr = curr.right;
	} else {
	TreeNode temp = curr.left;
	while (temp.right != null && temp.right != curr)
	temp = temp.right;
	if (temp.right == null) {
	temp.right = curr;
	curr = curr.left;
	} else {
	temp.right = null;
	res.add(curr.val);
	curr = curr.right;
	}
	}
	}
	return res;
	}
	}

view raw Morris inorder.java hosted with ❤ by GitHub

3. Postorder Traversal

在树的三种遍历方法中，后序永远是最难的，因为很难模拟第三次回到节点的情况。这在我们的iterative版本中已经说明。在Morris版本中，我们仍然可以沿用前序和后序的形式，不过要加一些代码来满足后序的要求。在Inorder中，我们第二次访问完了节点不会再回到当前节点，但是在后序版本中，当我们每次通过新添加的指针找到后继节点时，我们从当前节点c的左子结点开始到c的前驱结点，按逆序的方式加入结果集，来模拟第三次访问。值得注意的是，我们要加一个sentinel节点，并且把root设为他的左子结点，否则无法回收从root开始到最右边节点的一系列节点。

过程如下图所示(图片来自 Annie Kim's Blog)：

代码如下：

	/**
	* Definition for binary tree
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	public class Solution {
	public List<Integer> postorderTraversal(TreeNode root) {
	List<Integer> res = new ArrayList<Integer>();
	if (root == null)
	return res;
	TreeNode sentinel = new TreeNode(0);
	sentinel.left = root;
	TreeNode curr = sentinel;
	while (curr != null) {
	if (curr.left == null) {
	curr = curr.right;
	} else {
	TreeNode temp = curr.left;
	while (temp.right != null && temp.right != curr)
	temp = temp.right;
	if (temp.right == null) {
	temp.right = curr;
	curr = curr.left;
	} else {
	collect(res, curr.left, temp);
	temp.right = null;
	curr = curr.right;
	}
	}
	}
	return res;
	}
	private void collect(List<Integer> res, TreeNode from, TreeNode to) {
	reverse(from, to);
	TreeNode curr = to;
	while (curr != from) {
	res.add(curr.val);
	curr = curr.right;
	}
	res.add(from.val);
	reverse(to, from);
	}
	private void reverse(TreeNode from, TreeNode to) {
	TreeNode a = from, b = from.right;
	while (a != to) {
	TreeNode c = b.right;
	b.right = a;
	a = b;
	b = c;
	}
	}
	}

view raw Morris postorder.java hosted with ❤ by GitHub

下面我们来分析一下为什么后序按照这样的方式是对的。要分析后序的代码是不是对的，我们就要看当我们回收节点的时候是不是按照后序的要求来的。首先我们把所有节点分为两类：1. 当前节点c是父节点p的左子结点，2. c是p的右子结点。

对于所有的第一种节点，在我们第二次到达父节点的时候就会被回收。对于所有的第二种节点，当我们顺着当前找向上找是，一定会找到一个节点n，c在n的左子树（因为我们加入了sentinel节点，这个结论是必然的），那么，在我们回到n节点时，我们会把c节点连同他的父节点一起回收。所以我们肯定会遍历所有的节点。

当我们回收节点的时候，从当前节点的左子结点from到当前节点的前驱节点to的所有节点，他们的左子树都已经被遍历过，否则不会到达to节点。只剩下右子树没有遍历过，所以我们从to节点向from节点回收的过程是符合后序的顺序的，我们是先回收左子树在回收当前节点。

所以我们可以证明这个算法是正确的。

另外要注意的一点是，当我们回收from到to的节点时，不能用stack因为要求的是constant space。我们可以观察到从from到to节点其实就是一个链表结构，所以我们反转链表回收，之后再反转回来。

最后我们在讨论一下时间复杂度的问题，现在我们遍历的时候每次要找前驱结点，时间复杂度还是O(n)吗，下面我们来证明这个结论：

对于单个节点来说，找到他的前驱节点还是O(log n)。 但是如果我们要找所有的前驱节点，我们可以证明，对于任意两个不同的节点，从这个节点到前驱节点的路径不会有重复。路径分为两个部分: 1. 从节点到左子结点from 2. 从左子结点from一路向右到达t前驱结点to节点。首先任意路径的1部分是不会重合的，因为两个节点是不同的。第二任意节点的1和2也不会互相重复，因为1是到左子树的路径，2是到右子树的路径。最后两个不相同的节点他们的2部分也不会重合，如果有重合的部分，会找到相同的前驱节点，但是对于两个不同的节点，他们的前驱结点不可能相同。而对于二叉树来说，有n个节点会有n - 1条边，这些边最多会遍历三次：第一次是走到当前节点的时候，第二次是找前驱节点构建threaded binary tree的时候，第三次是恢复binary tree原始结构的时候。

通过下图可以更直观的理解证明(图片来自 Annie Kim's Blog):