北京治疗白癜风哪个医院专业 http://baidianfeng.39.net/bdfby/yqyy/前言
关乎二叉树遍历，最常见无外乎两种方法，一种递归（Recursion），一种迭代（BFS），两种办法都使用了栈这一数据结构，因此空间复杂度都是O(n)。然后嘞，小泉无意间看到了一种不使用栈的方法，并且使得空间复杂度降为了O(1)。
Morris遍历
先给大家叙说一下，Morris算法遍历的过程：对于当前节点cur
如果当前节点无左节点，访问当前节点右节点，即进行如下操作：
cur=cur.right;如果当前节点有左节点，找到当前节点cur左子树中最右的节点，记为mostRight2.1如果mostRight的右节点为空，则让mostRight的右节点指向当前节点cur，访问当前节点的左子节点即
mostRight.right=cur;cur=cur.left;2.2如果mostRight的右节点为当前节点cur，则让mostRight的右节点指向空然后访问当前节点的右子节点即
mostRight.right=null;cur=cur.right;算法模板
Morris(TreeNoderoot){//step:当前步nowPath:当前路径，path:当前步的后续可走的步TreeNodecur=root;TreeNodemostRight=null;while(cur!=null){mostRight=cur.left;//左子树if(mostRight!=null){//2while(mostRight.right!=nullmostRight.right!=cur){//左子树的最右节点mostRight=mostRight.right;}if(mostRIght.right==null){//2.1mostRight.right=cur;cur=cur.left;continue;}else{//2.2mostRight.right=null;}}cur=cur.right;//12.2}}算法流程解读
对于二叉树的遍历，其过程可以理解为如果无左子节点，那么整个过程只经过该节点一次；如果有左子节点，那么遍历经过其两次。
解释
根据Morris的规则
如果没有左子节点，那么就会从当前节点访问右子节点cur指向当前节点的右子节点，这就说明cur被更新，上一次的节点不会再得到访问，因此没有左子树的节点只有可能被访问一次。左子树最右节点的右子节点指向cur我们知道，遍历二叉树，从当前节点开始访问其左右子节点，那么不可避免的会涉及到==继续访问左子树再返回当前节点访问右子树==或者==继续访问右子树再返回当前节点访问左子树==。总之都会访问两次当前节点。那么同理，如果第二次到达左子树的最右节点意味着当前节点的左子树已经访问完毕了，当左子树访问完毕就需要回到当前节点。而左子树最右节点的子节点其实质上是一个叶子节点，Morris提出第一次到达最右节点就将其右子节点指向当前节点，就可以满足上述需求（可以理解为根据第一点解释从最右节点继续访问到当前节点，也可以理解为作为左子树访问完毕的验证条件）。
根据这两点，就使得Morris算法确实能够遍历二叉树。下面就以二叉树前序遍历和后序遍历为例子来进行小小的讲解吧。
二叉树遍历二叉树前序遍历
题目来源：二叉树前序遍历
问题描述★
Leetcode.二叉树前序遍历给你二叉树的根节点root，返回它节点值的前序遍历。输入：root=[1,null,2,3]输出：[1,2,3]
”问题分析
对于Morris来说，遍历的算法是固定的，那么就是如何输出前序遍历的列表。前序遍历节点输出为根左右那么Morris遍历：
如果没有左子树，保存当前节点值，然后访问当前节点右子树如果有左子树，让左子树的最右节点的右子节点指向当前节点，然后访问当前节点的左子树
这两点意味着访问第一次遍历的时候访问顺序为根-左-右，那么就在可能第一次遍历的地方将节点加入到列表里即可。那么如果是中序遍历该如何操作呢？（代码稍微有些不同，已在代码中注释）
代码Java版本
/***Definitionforabinarytreenode.*publicclassTreeNode{*intval;*TreeNodeleft;*TreeNoderight;*TreeNode(intx){val=x;}*}*/classSolution{publicListIntegerpreorderTraversal(TreeNoderoot){ListIntegerres=newArrayListInteger();if(root==null){returnres;}TreeNodecur=root,mostRIght=null;while(cur!=null){mostRIght=cur.left;if(mostRIght!=null){while(mostRIght.right!=nullmostRIght.right!=cur){mostRIght=mostRIght.right;}if(mostRIght.right==null){res.add(cur.val);mostRIght.right=cur;cur=cur.left;continue;}else{mostRIght.right=null;}}else{res.add(cur.val);}//如果是中序遍历则只需要在此处向res里添加个数就好res.add(cur.val);cur=cur.right;}returnres;}}二叉树的后序遍历
题目来源：二叉树的后序遍历
问题描述★
力扣给定一个二叉树，返回它的后序遍历。示例:输入:[1,null,2,3]1\2/3输出:[3,2,1]
”问题分析
其实这个过程是一致的，后序遍历稍微复杂一些是因为，每个节点最多访问两次，而且是按照根、左、右的访问顺序来的，而后序遍历则是左-右-根的顺序来的。那么对于后序遍历，在2.2时倒序输出从当前节点的左子节点到左子树最右节点这条路径上的所有节点。
代码Java版本
classSolution{publicListIntegerpostorderTraversal(TreeNoderoot){ListIntegerres=newArrayListInteger();if(root==null){returnres;}TreeNodecur=root,mostRight=null;while(cur!=null){mostRight=cur.left;if(mostRight!=null){while(mostRight.right!=nullmostRight.right!=cur){mostRight=mostRight.right;}if(mostRight.right==null){mostRight.right=cur;cur=cur.left;continue;}else{mostRight.right=null;addRes(res,cur.left);}}cur=cur.right;}addRes(res,root);returnres;}publicstaticvoidaddRes(ListIntegerres,TreeNodenode){TreeNodetail=reverseEdge(node);TreeNodecur=tail;while(cur!=null){res.add(cur.val);cur=cur.right;}reverseEdge(tail);}publicstaticTreeNodereverseEdge(TreeNodenode){TreeNodepre=null;TreeNodenext=null;while(node!=null){next=node.right;node.right=pre;pre=node;node=next;}returnpre;}}总结
Morris遍历算法初步讲解就到这里结束了，其实该算法的模板较为固定，理清Morris的遍历途径十分重要，而对于遍历顺序只需要搞清楚何时输出遍历值即可。
IT涓涓清泉
