文章目录
彩蛋题
奇数放奇数，偶数放偶数
双指针 设置奇数不对位置指针，设置偶数不对位置指针，两个指针都隔着格子来跳即可。
Morris遍历
它的意义
它可以实现非递归算法，以O(1)的空间复杂度来实现遍历树
morris遍历就即先走该节点的左子树，走完后借用动态添加的指针（类似线索二叉树）还会回到该节点，再走右子树
步骤（对于当前节点cur，可以结合eg理解）
- 如果cur无左树，cur=cur.right
- cur有左树，找到左树最右节点mostright
1） mostright右指针指向null的话，mostright.right=cur,cur=cur.left
2 ) mostright右指针指向当前节点的，让mostright.right=null
cur=cur.right
eg（利用底层空闲指针回到上层）
cur在1节点，其有左树，找到左树的最右节点5，其右指针指向该节点，cur=cur.left(1)
cur在2节点，其有左树，找到左树的最右节点4，其右指针指向该节点，cur=cur.left(12)
cur在4节点，其没有左树，cur=cur.right(124)
cur在2节点，其有左树，且左树的最右节点的右指针指向本节点，因此删除该右指针，cur=cur.right (1242)
cur在5节点，其没有左树，cur=cur.right(12425)
cur在1节点，其有左树，且左树的最右节点的右指针指向该节点，故删除该指针，cur=cur.right (124251)
cur在3节点，有左子树，其左子树的最右节点右指针指向当前节点，cur=cur.left（1242513）
cur在6节点，没有左子树， cur=cur.left （12425136）
cur在3节点，其有左树，且左树的最右节点的右指针指向该节点，故删除该指针，cur=cur.right（124251363）
cur在7节点，其无左子树，cur=cur.right,结束（1242513637）
无左树，向右走
有左树，加指针，向左走 通过这个指针后回到该节点后删除 向右走
morris遍历就是有左树的节点都会遍历两次，即先走该节点的左子树，走完后还会回来，然后删除额外的指针。
时间复杂度O(N)的证明
每个节点有左子树都要找左子树的右边界，这还是O(N)??
找1的右边界，需要遍历2 5 11
找2的右边界，需要遍历4 9
…
我们会发现，每个数的右边界是不重叠的，基本就等于最后多走了常数项遍树。所以
空 间 复 杂 度 O ( N ) 空间复杂度O(N) 空间复杂度O(N)
morris代码
public class treenode{
int val;
treenode left;
treenode right;
}
public void morriswalk(treenode root)
{
treenode cur=root;
treenode mostright=root;
while(cur!=null)
{
if(cur.left==null)//cur无左子树
{
cur=cur.right;
}
else
{
mostright=root.left;
while(mostright.right!=null&&mostright.right!=cur)
{
mostright=mostright.right;
}
if(mostright.right==null)//cur有左子树，且第一次遍历
{
mostright.right=cur;
cur=cur.left;
}
else//cur有左子树，第二次遍历
{
mostright.right=null;
cur=cur.right;
}
}
}
}
MORRIS转成先序
第一次遇到有左树的就打印，第二次遇到不打印
MORRIS转成中序
第一次遇到有左树的不打印，第二次遇到打印
MORRIS转成后序
关于后序遍历的tips：
因此
- 每当第二次遍历一个节点时，逆序输出其左子树的右边界
- 输出整个树的右边界
逆序输出右边界时如何保持空间复杂度为O(1)?
用栈？不行
答案是翻转链表，先翻转一遍，从底端输出到头部，再翻转过来。
由于右边界并不重叠，所以时间复杂度仍是增加常数个N,仍为
O ( N ) O(N) O(N)
后序morris代码
public class morris {
public static class treenode{
int val;
treenode left;
treenode right;
public treenode(int val)
{
this.val=val;
}
}
//tested
//输出该节点的右边界（包含该节点）
public static void printright(treenode root)
{
treenode p=root;
while(p!=null)
{
System.out.print(p.val+" ");
p=p.right;
}
}
//tested
//翻转该节点的右边界(包含该节点),返回新的头结点
public static treenode reverse(treenode root)
{
// 1 ->3 ->7
if(root==null||root.right==null)
{
return root;
}
treenode p=root;//p是上一个节点
treenode q=root.right;//q是当前节点，需要把当前节点连上上一个节点
p.right=null;
treenode l=null;//存储更新q的
while(q!=null)
{
l=q.right;
q.right=p;
p=q;
q=l;
}
return p;
}
//tested
//morris遍历树，后序输出
public static void morriswalk(treenode root)
{
treenode cur=root;
treenode mostright=root;
while(cur!=null)
{
if(cur.left==null)//cur无左子树
{
cur=cur.right;
}
else
{
mostright=cur.left;
while(mostright.right!=null&&mostright.right!=cur)
{
mostright=mostright.right;
}
if(mostright.right==null)//cur有左子树，且第一次遍历
{
mostright.right=cur;
cur=cur.left;
}
else//cur有左子树，第二次遍历
{
//注意要先删除mostright的连接cur的指针，再输出右边界
mostright.right=null;
reverse(cur.left);
printright(mostright);
reverse(mostright);
cur=cur.right;
}
}
}
treenode t=reverse(root);
printright(t);
reverse(t);
}
public static void main(String[] args) {
treenode a=new treenode(1);
treenode b=new treenode(2);
treenode c=new treenode(3);
treenode d=new treenode(4);
treenode e=new treenode(5);
treenode f=new treenode(6);
treenode g=new treenode(7);
a.left=b;
a.right=c;
b.left=d;
b.right=e;
c.left=f;
c.right=g;
morriswalk(a);
}
}