遍历二叉树的Morris序
2023-12-24 13:16:01
参考书:《程序员代码面试指南》
这种方法的好处在于,它做到了时间复杂度为O(n),额外空间复杂度为O(1)(只申请几个变量就可以完成整个二叉树的遍历)。
Morris遍历时cur访问节点的顺序就是morris序,可以在Morris序的基础上加工出前序遍历序列、中序遍历序列、后序遍历序列。
对于前序、中序,你只需要看要在Morris遍历过程中的合适位置加打印动作即可。
而对于后序,比较复杂。
下面举个例子,说明Morris遍历和对应的加工。
对于上图的二叉树来说,Morris序就是 cur访问过的顺序:1,2,4,2,5,1,3,6,3,7.
前序遍历序列就是第一次访问的顺序:1,2,4,5,3,6,7。
中序遍历序列就是第二次访问(附注:如果一个节点只被访问一次,那么第一次访问时直接打印)的顺序:4,2,5,1,6,3,7。
后序遍历序列是,每次恢复现场(恢复空闲指针)时,逆向打印cur的左子树的右边界;最后,逆序打印整个树的右边界,下面给出详细说明:
第一次恢复现场时,cur=②,逆向打印其左树的右边界:4;
第二次恢复现场时,cur=①,逆向打印其左树的右边界:5,2;
第三次恢复现场时,cur=③,逆向打印其左树的右边界:6;
最后,逆序打印整个树的右边界:7,3,1;
所以,整个后序遍历序列是 4,5,2,6,7,3,1.
public class Morris {
public void morris(TreeNode head){// morris遍历
TreeNode cur=head;
TreeNode rightMost=null;
while (cur!=null){
rightMost=cur.left;
if(rightMost!=null){
while (rightMost.right!=null&&rightMost.right!=cur){
rightMost=rightMost.right;
}
if(rightMost.right==null){
rightMost.right=cur;
cur=cur.left;
continue;
}
if(rightMost.right==cur){
rightMost.right=null;
cur=cur.right;
continue;
}
}else {
cur=cur.right;
}
}
}
public static void morrisPreTraversal(TreeNode head){
TreeNode cur=head;
TreeNode rightMost=null;
while (cur!=null){
rightMost=cur.left;
if(rightMost!=null){
while (rightMost.right!=null&&rightMost.right!=cur){
rightMost=rightMost.right;
}
if(rightMost.right==null){
rightMost.right=cur;
System.out.println(cur.value);
cur=cur.left;
continue;
}
if(rightMost.right==cur){
rightMost.right=null;
cur=cur.right;
continue;
}
}else {
System.out.println(cur.value);
cur=cur.right;
}
}
}
public static void morrisInTraversal(TreeNode head){
TreeNode cur=head;
TreeNode rightMost=null;
while (cur!=null){
rightMost=cur.left;
if(rightMost!=null){
while (rightMost.right!=null&&rightMost.right!=cur){
rightMost=rightMost.right;
}
if(rightMost.right==null){
rightMost.right=cur;
cur=cur.left;
continue;
}
if(rightMost.right==cur){
rightMost.right=null;
System.out.println(cur.value);
cur=cur.right;
continue;
}
}else {
System.out.println(cur.value);
cur=cur.right;
}
}
}
public static void morrisPostTraversal(TreeNode head){
TreeNode cur=head;
TreeNode rightMost=null;
while (cur!=null){
rightMost=cur.left;
if(rightMost!=null){
while (rightMost.right!=null&&rightMost.right!=cur){
rightMost=rightMost.right;
}
if(rightMost.right==null){
rightMost.right=cur;
cur=cur.left;
continue;
}
if(rightMost.right==cur){
rightMost.right=null;
printReverseRB(cur.left);
cur=cur.right;
continue;
}
}else {
cur=cur.right;
}
}
printReverseRB(head);
}
private static void printReverseRB(TreeNode head) {
TreeNode next=null;
TreeNode cur=head;
TreeNode pre=null;
pre=reverseEdge(cur);
cur=pre;
while (cur!=null){
System.out.println(cur.value);
cur=cur.right;
}
// restore
reverseEdge(pre);
}
private static TreeNode reverseEdge(TreeNode head){
TreeNode next=null;
TreeNode cur=head;
TreeNode pre=null;
while (cur!=null){
next=cur.right;
cur.right=pre;
pre=cur;
cur=next;
}
return pre;
}
public static void main(String[] args) {
TreeNode head=new TreeNode(1);
head.left=new TreeNode(2);
head.right=new TreeNode(3);
head.left.left=new TreeNode(4);
head.left.right=new TreeNode(5);
head.right.left=new TreeNode(6);
head.right.right=new TreeNode(7);
morrisPreTraversal(head);
System.out.println();
morrisInTraversal(head);
System.out.println();
morrisPostTraversal(head);
}
}
class TreeNode{
TreeNode right;
TreeNode left;
int value;
public TreeNode(int val){
this.value=val;
this.right=null;
this.left=null;
}
}
文章来源:https://blog.csdn.net/qq_43448491/article/details/135179570
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!