二叉树Morris遍历

二叉树Morris遍历代码：

	public int[] Morris(TreeNode head) {//得到Morris序
		List list=new ArrayList();;//存放Morris序
		if(head==null)return null;
		TreeNode cur=head;
		TreeNode mostRightNode=null;
		while(cur!=null) {
			list.add(cur.value);
			mostRightNode=cur.left;
			if(mostRightNode!=null) {
				while(mostRightNode.right!=null&&mostRightNode.right!=cur) {
					mostRightNode=mostRightNode.right;
				}
				if(mostRightNode.right==null) {//第一次遍历到cur结点
					mostRightNode.right=cur;
					cur=cur.left;
					continue;
				}
				else {//第二次遍历到cur结点
					mostRightNode.right=null;
					
				}
			}
			cur=cur.right;
			
		}
		int[] ans=new int[list.size()];
		for(int i=0;i 
Morris改二叉树前序遍历代码：
 Leetcode上AC了
 
class Solution {
    
    public List preorderTraversal(TreeNode root) {
        List list=new ArrayList();
		if(root==null)return list;
		TreeNode cur=root;
		TreeNode mostRightNode=null;
		while(cur!=null) {
			mostRightNode=cur.left;
			if(mostRightNode!=null) {
				while(mostRightNode.right!=null&&mostRightNode.right!=cur) {
					mostRightNode=mostRightNode.right;
				}
				if(mostRightNode.right==null) {
					list.add(cur.val);
					mostRightNode.right=cur;
					cur=cur.left;
					continue;
				}
				else {
					mostRightNode.right=null;
				}
			}
			else {
				list.add(cur.val);
			}
			cur=cur.right;
		}
        return list;
        
    }
}
 
 
 
Morris改二叉树中序遍历代码：
 
class Solution {
    public List inorderTraversal(TreeNode root) {
        List list=new ArrayList();
		if(root==null)return list;
		TreeNode cur=root;
		TreeNode mostRightNode=null;
		while(cur!=null) {
			mostRightNode=cur.left;
			if(mostRightNode!=null) {
				while(mostRightNode.right!=null&&mostRightNode.right!=cur) {
					mostRightNode=mostRightNode.right;
				}
				if(mostRightNode.right==null) {
					mostRightNode.right=cur;
					cur=cur.left;
					continue;
				}
				else {
					mostRightNode.right=null;
				}
			}
			
			list.add(cur.val);
			cur=cur.right;
			
		}
		return list;
    }
}
 

 
 
Morris改二叉树后序遍历代码：
 
class Solution {
    public static void collectNodes(TreeNode head,List list) {//以head为头，逆序收集该树的右边界结点
		TreeNode rear=reverseTree(head);
		TreeNode cur=rear;
		while(cur!=null) {
			list.add(cur.val);
			cur=cur.right;
		}
		reverseTree(rear);
	}
	public static TreeNode reverseTree(TreeNode from) {//逆序
		TreeNode pre=null;
		TreeNode next=null;
		while(from!=null) {
			next=from.right;
			from.right=pre;
			pre=from;
			from=next;
		}
		return pre;
	}
    public List postorderTraversal(TreeNode root) {
        List list=new ArrayList();;//存放Morris序
		if(root==null)return list;
		TreeNode cur=root;
		TreeNode mostRightNode=null;
		while(cur!=null) {
//			list.add(cur.value);
			mostRightNode=cur.left;
			if(mostRightNode!=null) {
				while(mostRightNode.right!=null&&mostRightNode.right!=cur) {
					mostRightNode=mostRightNode.right;
				}
				if(mostRightNode.right==null) {//第一次遍历到cur结点
					mostRightNode.right=cur;
					cur=cur.left;
					continue;
				}
				else {//第二次遍历到cur结点
					
					mostRightNode.right=null;
					collectNodes(cur.left,list);//收集第二次遍历到的点的左子树结点
				}
			}
			cur=cur.right;
			
		}
		collectNodes(root,list);//收集整棵树的右边界结点
		return list;
    }
}
 

 
 
视频链接：
 https://space.bilibili.com/384453285