vlambda博客
学习文章列表

之前介绍过二叉树的前中后，以及DFS和BFS等遍历方式，并且每种都写了递归和非递归的解法。有的说二叉树的前中后遍历方式都属于DFS的一种，其实也可以这样理解。关于这几种遍历方式具体可以看下。

对于二叉树的遍历除了前面介绍的几种常见的以外，还有Morris的前中后3种遍历方式。前面讲的二叉树的几种遍历方式，如果使用的是非递归方式，我们要么需要一个栈，要么需要一个队列来维护节点之间的关系。如果使用Morris遍历就不需要了，他的实现过程其实就是把叶子节点的指针给利用起来，因为一般情况下，二叉树的叶子节点是没有子节点的，也就是说他们是指向空，这样总感觉有点浪费，Morris的实现原理其实就是把叶子节点的指针给利用了起来。Morris的后续遍历方式稍微有点复杂，这个以后再讲，这里主要看一下Morris的前序和中序遍历方式。

对于Morris的中序遍历可以把它看做是把二叉树拉直变成了链表，我们先来看一下他的实现步骤：

记当前节点为cur，从根节点开始遍历。

1，判断cur是否为空，如果为空就停止遍历。

2，如果cur不为空

    1）如果cur没有左子节点，打印cur的值，然后让cur指向他的右子节点，即cur=cur.right

    2）如果cur有左子节点，则从左子节点中找到最右边的结点pre。

       1))如果pre的右子节点为空，就让pre的右子节点指向cur，即pre.right=cur，然后cur指向他的左子节点，即cur=cur.left。

      2))如果pre的右子节点不为空，就让他指向空，即pre.right=null，然后输出cur节点的值，并将节点cur指向其右子节点，即cur=cur.right。

3，重复步骤2，直到节点cur为空为止。

上面叙述了一大堆，懂的一眼就能看明白，不懂的肯定会绕晕。我来一条条解释一下。

1，首先第一条，cur为空就停止遍历，这没什么好说的，为空了当然就没法遍历了。

2，cur不为空，cur的左子节点为空，打印当前节点cur的值，然后让cur=cur.right，我们来画个图看一下

2，cur不为空，他的左子节点也不为空，我们要找到他左子节点中的最右子节点pre，其实也就是中序遍历中cur的前一个节点，我们随便画两棵树来看一下，很明显就是要找到当前节点cur在中序遍历的前一个节点。

然后判断pre的右子节点是否为空，这一步可能是大家最疑惑的地方，这还需要判断吗，其实是需要的，第一次查找的时候，pre的右子节点肯定是为空的，我们让他指向cur即可，也就是pre.right=cur。如下图所示

然后再让cur指向他的左子节点，如下图所示

虽然节点1和他的左子节点没有断开，但我们可以认为他是断开了（实际上没有断开），我们可以把它想象成这样

最终我们可以把它想象成转化为一个链表（实际上并没有）。

如果pre的右子节点不为空，那么他肯定是指向cur节点的，也就表示cur节点的左子节点都已经遍历完了，只需要打印当前节点cur的值，然后让cur指向右子节点，以同样的操作开始遍历右子节点。

文字描述比较绕，我们就随便举个例子画个图来看下

搞懂了上面的原理，代码就简单多了

 1public List<Integer> inorderTraversal(TreeNode root) {
 2    List<Integer> res = new ArrayList<>();
 3    //首先把根节点赋值给cur
 4    TreeNode cur = root;
 5    //如果cur不为空就继续遍历
 6    while (cur != null) {
 7        if (cur.left == null) {
 8            //如果当前节点cur的左子节点为空，就访问当前节点cur，
 9            //接着让当前节点cur指向他的右子节点
10            res.add(cur.val);
11            cur = cur.right;
12        } else {
13            TreeNode pre = cur.left;
14            //查找pre节点，注意这里有个判断就是pre的右子节点不能等于cur
15            while (pre.right != null && pre.right != cur)
16                pre = pre.right;
17            //如果pre节点的右指针指向空，我们就让他指向当前节点cur，
18            //然后当前节点cur指向他的左子节点
19            if (pre.right == null) {
20                pre.right = cur;
21                cur = cur.left;
22            } else {
23                //如果pre节点的右指针不为空，那么他肯定是指向cur的,
24                //表示cur的左子节点都遍历完了，我们需要让pre的右
25                //指针指向null，目的是把树给还原，然后再访问当前节点
26                //cur，最后再让当前节点cur指向他的右子节点。
27                pre.right = null;
28                res.add(cur.val);
29                cur = cur.right;
30            }
31        }
32    }
33    return res;
34}

前序遍历和中序遍历的方式是一样的，只不过访问节点的时机不一样。图就不在画了，代码中有注释，可以看下

 1public List<Integer> preorderTraversal(TreeNode root) {
 2    List<Integer> res = new ArrayList<>();
 3    //首先把根节点赋值给cur
 4    TreeNode cur = root;
 5    //如果cur不为空就继续遍历
 6    while (cur != null) {
 7        if (cur.left == null) {
 8            //如果当前节点cur的左子节点为空，就访问当前节点cur，
 9            //接着让当前节点cur指向他的右子节点
10            res.add(cur.val);
11            cur = cur.right;
12        } else {
13            TreeNode pre = cur.left;
14            //查找pre节点，注意这里有个判断就是pre的右子节点不能等于cur
15            while (pre.right != null && pre.right != cur)
16                pre = pre.right;
17            //如果pre节点的右指针指向空，我们就让他指向当前节点cur，
18            //然后打印当前节点cur的值，最后再让当前节点cur指向他的左子节点
19            if (pre.right == null) {
20                pre.right = cur;
21                res.add(cur.val);
22                cur = cur.left;
23            } else {
24                //如果pre节点的右指针不为空，那么他肯定是指向cur的,
25                //表示当前节点cur和他的的左子节点都遍历完了，直接
26                //让他指向他的右子节点即可。
27                pre.right = null;
28                cur = cur.right;
29            }
30        }
31    }
32    return res;
33}

上面就是Morris的中序和前序遍历，关于后续遍历有一点复杂，后面单独有一篇文章来讲。