Morris算法进行二叉树遍历

比眉伴天荒 2022-08-08 07:00 14阅读 0赞

二叉树作为计算机中的一个重要数据结构，在很多领域都会涉及到，而提到二叉树，我们首先想到的就是其3种遍历方式--前序、中序和后序，对于这三种遍历方式，我们很容易通过使用递归或者迭代（http://blog.csdn.net/yangfeisc/article/details/44497429）的方式实现，时间复杂度为O(N)。但是这两种实现方式都需要使用堆栈进行节点信息的存储，即空间复杂度也是O(N)。

但是还有一种更为巧妙的遍历方法--Morris算法，该算法的时间复杂度也是O(N)，但是空间复杂度却能达到最优的O(1)。下面根据二叉树的三种遍历方式详细介绍Morris算法。

树的节点定义如下：

public class TreeNode {
    	int val;
            TreeNode left;
            TreeNode right;
            TreeNode(int x) { 
                val = x; 
    	}
        }

一、中序遍历：

算法步骤：

1. 如果当前节点的左子节点为空时，输出当前节点，并将当前节点置为该节点的右子节点；

2. 如果当前节点的左子节点不为空，找到当前节点左子树的最右节点（该节点为当前节点中序遍历的前驱节点）；

2.1. 如果最右节点的右指针为空(right=null)，将最右节点的右指针指向当前节点，当前节点置为其左子节点；

2.2. 如果最右节点的右指针不为空，将最右节点右指针重新置为空(恢复树的原状)，输出当前节点，并将当前节点置为其右节点；

3. 重复1~2，直到当前节点为空。

下图显示了Morris算法中序遍历的过程。

![Center][]

Java实现如下：

public List<Integer> Morris_InOrder(TreeNode root) {
    	List<Integer> res = new ArrayList<>();
    	if(root == null)
    		return res;
    	TreeNode cur = root;
    	while(cur != null) {
    		if(cur.left == null) {
    			res.add(cur.val);
    			cur = cur.right;
    		} else {
    			TreeNode tmp = cur.left;
    			while(tmp.right != null && tmp.right != cur)
    				tmp = tmp.right;
    			if(tmp.right == null) {
    				tmp.right = cur;  //找到当前节点的前驱节点
    				cur = cur.left;
    			} else {
    				res.add(cur.val);
    				tmp.right = null;  //恢复二叉树
    				cur = cur.right;
    			}
    		}
    	}
    	return res;
    }

二、前序遍历，前序遍历的基本思想和中序遍历很相似，只有输出顺序发生变化。

算法步骤：

1. 如果当前节点的左子节点为空时，输出当前节点，并将当前节点置为该节点的右子节点；

2. 如果当前节点的左子节点不为空，找到当前节点左子树的最右节点（该节点为当前节点中序遍历的前驱节点）；

2.1. 如果最右节点的右指针为空(right=null)，将最右节点的右指针指向当前节点，**并输出当前节点（在此处输出）**，当前节点置为其左子节点；

2.2. 如果最右节点的右指针不为空，将最右节点右指针重新置为空(恢复树的原状)，并将当前节点置为其右节点；

3. 重复1~2，直到当前节点为空。

下图显示了Morris算法前序遍历的过程：

![Center 1][]

Java实现如下：

public List<Integer> Morris_PreOrder(TreeNode root) {
    	List<Integer> res = new ArrayList<>();
    	if(root == null)
    		return res;
    	TreeNode cur = root;
    	while(cur != null) {
    		if(cur.left == null) {
    			res.add(cur.val);
    			cur = cur.right;
    		} else {
    			TreeNode tmp = cur.left;
    			while(tmp.right != null && tmp.right != cur)
    				tmp = tmp.right;
    			if(tmp.right == null) {
    				res.add(cur.val); //输出当前节点
    				tmp.right = cur;  //找到当前节点的前驱节点
    				cur = cur.left;
    			} else {
    				tmp.right = null;  //恢复二叉树
    				cur = cur.right;
    			}
    		}
    	}
    	return res;
    }

三、后序遍历：后序遍历较前两者比较麻烦，**需要建立一个临时节点，并令该节点的左子节点为root**，并且需要一个子过程，倒序输出某两个节点之间路径上的各个节点。

算法步骤：

1. 如果当前节点的左子节点为空时，则将其右子节点作为当前节点；

2. 如果当前节点的左子节点不为空，找到当前节点左子树的最右节点（该节点为当前节点中序遍历的前驱节点）；

2.1. 如果最右节点的右指针为空(right=null)，将最右节点的右指针指向当前节点，当前节点置为其左子节点；

2.2. 如果最右节点的右指针不为空，将最右节点右指针重新置为空(恢复树的原状)，倒序输出从当前节点的左子节点到该最右节点路径上的所有节点，并将当前节点置为其右节点；

3. 重复1~2，直到当前节点为空。

下图显示了Morris算法后序遍历过程(其中虚线框内的节点为临时节点)：

![Center 2][]

Java实现如下：

public List<Integer> Morris_PostOrder(TreeNode root) {
    	List<Integer> res = new ArrayList<>();
    	if(root == null)
    		return res;
    	TreeNode virNode = new TreeNode(-1);  //建立临时节点
    	virNode.left = root;    //设置临时节点的左子节点为根节点
    	TreeNode cur = virNode;
    	while(cur != null) {
    		if(cur.left == null) {
    			cur = cur.right;
    		} else {
    			TreeNode tmp = cur.left;
    			while(tmp.right != null && tmp.right != cur)
    				tmp = tmp.right;
    			if(tmp.right == null) {
    				tmp.right = cur;  //找到当前节点的前驱节点
    				cur = cur.left;
    			} else {
    				tmp.right = null;  //恢复二叉树
    				TreeNode t = cur.left;  
    				List<Integer> tmpList = new ArrayList<>();
    				while(t != null) {  //倒序输出当前节点左子节点到当前节点前驱节点路径上的所有节点
    					tmpList.add(0, t.val);
    					t = t.right;
    				}
    				res.addAll(tmpList);
    				cur = cur.right;
    			}
    		}
    	}
    	return res;
    }

[Center]: /images/20220805/29c928732ae64d3abb1fce8614ba1324.png
[Center 1]: /images/20220805/0c3d9957231a4390b86a0d87b67f94e4.png
[Center 2]: /images/20220805/39deacaaecd0411381bc75d4e3ae0764.png