Morris遍历细节：
假设cur来到当前节点，cur从头节点开始
1、cur没有左孩子，cur向右移动
2、cur有左孩子，找到左孩子的最右孩子
a:如果右孩子的右指针为空，则让右指针指向当前节点，当前节点向左移动,回到1;(表示第一次到这个节点)
b:如果右孩子的右指针指向当前节点，让右指针指向null,当前节点向右移动；（表示第二次到这个节点）
3、当cur为空遍历结束
这个过程说明了：如果cur有左孩子遍历时会两次经过该节点， 否则只会一次经过该节点
Morris遍历的优势：优化了空间复杂度，O（1），时间复杂度O（N）
树和的遍历相关都以Morris遍历为最优解
/**
* Morris遍历
*/
public void morrisTraversal(TreeNode head){
if(head==null) {
return;
}
TreeNode cur=head;
TreeNode mostRight;
while(cur!=null){
mostRight=cur.left;
if(mostRight!=null){
//有左节点
while (mostRight.right!=null&&mostRight.right!=cur){
mostRight=mostRight.right;
}
//会来到cur两次
if(mostRight.right==null){
//第一次来到cur
mostRight.right=cur;
cur=cur.left;
continue;
}else{
//第二次来到cur
mostRight.right=null;
}
}
//只会来到cur一次，或第二次来到cur都会来到这里,往右移动
cur=cur.right;
}
}
/**
改先序遍历：第一次来到cur就打印
*/
public void preOrderTraversal(TreeNode head){
if(head==null) {
return;
}
TreeNode cur=head;
TreeNode mostRight;
while(cur!=null){
mostRight=cur.left;
if(mostRight!=null){
//有左节点
while (mostRight.right!=null&&mostRight.right!=cur){
mostRight=mostRight.right;
}
//会来到cur两次
if(mostRight.right==null){
//第一次来到cur就打印
//注意这行的位置，不能放到下面，因为cur会移动
System.out.println(cur.val);
mostRight.right=cur;
cur=cur.left;
continue;
}else{
//第二次来到cur
mostRight.right=null;
}
}else{
//只会来到一次的cur打印
System.out.println(cur.val);
}
//只会来到cur一次，或第二次来到cur都会来到这里,往右移动
cur=cur.right;
}
}
/**
改中序遍历：
1、如果会来到cur两次，则第二次来到cur时打印
2、只会来到一次的，直接打印
*/
public void inOrderTraversal(TreeNode head){
if(head==null) {
return;
}
TreeNode cur=head;
TreeNode mostRight;
while(cur!=null){
mostRight=cur.left;
if(mostRight!=null){
//有左节点
while (mostRight.right!=null&&mostRight.right!=cur){
mostRight=mostRight.right;
}
//会来到cur两次
if(mostRight.right==null){
//第一次来到cur
mostRight.right=cur;
cur=cur.left;
continue;
}else{
//第二次来到cur
mostRight.right=null;
}
}
//只会来到cur一次，或第二次来到cur都会来到这里,往右移动
System.out.println(cur.val);
cur=cur.right;
}
}
/**
改后序遍历：
1、处理时机在第二次来到cur时：逆序打印左树的右边界
2、最后逆序打印整颗树的右边界
*/
public void postMorris(TreeNode head){
if(head==null){
return;
}
TreeNode cur=head;
TreeNode mostRight;
while (cur!=null){
mostRight=cur.left;
if(mostRight!=null){
while (mostRight.right!=null&&mostRight.right!=cur){
mostRight=mostRight.right;
}
if(mostRight.right==null){
mostRight.right=cur;
cur=cur.left;
continue;
}else{
//第二次来到cur
mostRight.right=null;
//处理时机在第二次来到cur时，逆序打印在孩子的右边界
processEdge(cur.left);
}
}
cur=cur.right;
}
//最后逆序打印整颗树的右边界
processEdge(head);
}
/**
* 逆序打印处理，处理完再逆序回来
*/
public void processEdge(TreeNode head){
TreeNode tail=reverse(head);
TreeNode cur=tail;
while (cur!=null){
System.out.println(cur.val);
cur=cur.right;
}
reverse(tail);
}
/**
*
相当于单链表反转，把right指针当作是next指针
*/
public TreeNode reverse(TreeNode head){
if(head==null||head.right==null){
return head;
}
TreeNode pre=null;
TreeNode next;
TreeNode cur=head;
while (cur!=null){
next=cur.right;
cur.right=pre;
pre=cur;
cur=next;
}
return pre;
}
Morris遍历