二叉树的非递归遍历算法

1. 广度优先遍历
   采用队列，取出当初层对应的所有节点，并将其所有子节点依次加入队列

public List> levelOrder(TreeNode root) {
	ArrayList> list = new ArrayList>();
	if(root == null)
		return list;
	Queue que = new linkedList();
	que.offer(root);
	while(que.size()!=0){
		int len = que.size();
		ArrayList subList = new ArrayList();
		for(int i = 0; i < len; i++){   \遍历当初层的元素并将其子节点加入队列中
		root = que.poll();
		subList.add(root.val);
		if(root.left != null){
			que.offer(root.left);
		}
		if(root.right != null){
			que.offer(root.right);  
		}       
	}
	list.add(subList);
}
return list;
}

上面的递归算法需要用到栈的结构，使用Morris遍历算法可以将算法的时间复杂度降低到
2. 深度优先遍历
深度优先遍历有三种顺序：先序遍历（中左右），中序遍历（左中右），后序遍历（左右中）。
这三种遍历方式不同的只有头节点的遍历顺序，左子树都先与右子树遍历。当用栈来模拟递归程序时，都是先头节点进栈、然后左子树进栈，最后右子树进栈，不同的只是头节点的访问顺序(头节点在左子树进栈前访问，头节点在左子树进栈后并且在右子树进栈前访问，头节点在右子树进栈后访问)。在访问左子树时，需要对左子树的左子树进行访问，访问左子树的左子树时又要对左子树的左子树的左子树进行访问，这样第一次进行某个右子树的处理是在处理完最左的子树之后。于是得到如下的算法框架：

 
 public List traversal(TreeNode root) {
        linkedList list = new linkedList();
        if(root == null)
        	return list;
        Stack stack = new Stack();
        TreeNode temp, pre;	//pre用来记录上一个处理的节点，temp用来记录当前要处理的节点
        temp = root; pre = null;
        while(temp != null || !stack.isEmpty()){
		
			while(temp != null){	//找到当前节点的最左的子节点并依次进栈
			
				stack.push(temp);
				temp = temp.left;
			}
        	temp = stack.peek();	//获得栈顶元素，栈顶元素一定满足没有左子树或者左子树已经被处理
        	if(temp.right == null || temp.right == pre){	//当前节点的右子树已处理或者没有右子树
        	
        		stack.pop();	//退栈
        		pre = temp;
        		temp = null; //当前节点对应的子树处理完毕
        	}else{	//处理右子树
        		
        		temp = temp.right;
        	}
        }
        return list;
    }

先序遍历时，头节点先于左子树和右子树处理

 public List traversal(TreeNode root) {
        linkedList list = new linkedList();
        if(root == null)
        	return list;
        Stack stack = new Stack();
        TreeNode temp, pre;	//pre用来记录上一个处理的节点，temp用来记录当前要处理的节点
        temp = root; pre = null;
        while(temp != null || !stack.isEmpty()){
		
			while(temp != null){	//找到当前节点的最左的子节点并依次进栈
				list.add(temp.val);	//头结点先于左子树处理
				stack.push(temp);
				temp = temp.left;
			}
        	temp = stack.peek();	//获得栈顶元素，栈顶元素一定满足没有左子树或者左子树已经被处理
        	if(temp.right == null || temp.right == pre){	//当前节点的右子树已处理或者没有右子树
        	
        		stack.pop();	//退栈
        		pre = temp;
        		temp = null; //当前节点对应的子树处理完毕
        	}else{	//处理右子树
        		
        		temp = temp.right;
        	}
        }
        return list;
    }

 public List traversal(TreeNode root) {
        linkedList list = new linkedList();
        if(root == null)
        	return list;
        Stack stack = new Stack();
        TreeNode temp;	//temp用来记录当前要处理的节点
        temp = root;
        while(temp != null || !stack.isEmpty()){
		
			while(temp != null){	//找到当前节点的最左的子节点并依次进栈
				list.add(temp.val);	//头结点先于左子树处理
				stack.push(temp);
				temp = temp.left;
			}
			
        	temp = stack.pop();	
        	temp = temp.right;
        }
        return list;
    }

中序遍历时，头节点先于右子树后于左子树处理

 public List traversal(TreeNode root) {
        linkedList list = new linkedList();
        if(root == null)
        	return list;
        Stack stack = new Stack();
        TreeNode temp, pre;	//pre用来记录上一个处理的节点，temp用来记录当前要处理的节点
        temp = root; pre = null;
        while(temp != null || !stack.isEmpty()){
		
			while(temp != null){	//找到当前节点的最左的子节点并依次进栈
				stack.push(temp);
				temp = temp.left;
			}
        	temp = stack.peek();	//获得栈顶元素，栈顶元素一定满足没有左子树或者左子树已经被处理
        	if(temp.right == null || temp.right == pre){	//当前节点的右子树已处理或者没有右子树
        		if(temp.right == null)//此时右子树还没处理
        			list.add(temp.val);
        		stack.pop();	//退栈
        		pre = temp;
        		temp = null; //当前节点对应的子树处理完毕
        	}else{	//处理右子树
        		list.add(temp.val); //处理头节点
        		temp = temp.right;
        	}
        }
        return list;
    }

 public List traversal(TreeNode root) {
        linkedList list = new linkedList();
        if(root == null)
        	return list;
        Stack stack = new Stack();
        TreeNode temp, pre;	//pre用来记录上一个处理的节点，temp用来记录当前要处理的节点
        temp = root; pre = null;
        while(temp != null || !stack.isEmpty()){
		
			while(temp != null){	//找到当前节点的最左的子节点并依次进栈
				stack.push(temp);
				temp = temp.left;
			}
			
        	temp = stack.pop();	
        	list.add(temp.val);
			temp = temp.right;
		}
        return list;
    }

后序遍历时，头节点在右子树遍历后访问

 public List traversal(TreeNode root) {
        linkedList list = new linkedList();
        if(root == null)
        	return list;
        Stack stack = new Stack();
        TreeNode temp, pre;	//pre用来记录上一个处理的节点，temp用来记录当前要处理的节点
        temp = root; pre = null;
        while(temp != null || !stack.isEmpty()){
		
			while(temp != null){	//找到当前节点的最左的子节点并依次进栈
				stack.push(temp);
				temp = temp.left;
			}
        	temp = stack.peek();	//获得栈顶元素，栈顶元素一定满足没有左子树或者左子树已经被处理
        	if(temp.right == null || temp.right == pre){	//当前节点的右子树已处理或者没有右子树
        	
        	    list.add(temp.val);	//temp.right == null时，右子树为空无需处理；temp.right == pre时，右子树处理完毕
        		stack.pop();	//退栈
        		pre = temp;
        		temp = null; //当前节点对应的子树处理完毕
        	}else{	//处理右子树
        		temp = temp.right;
        	}
        }
        return list;
    }

上面需要用到栈，空间复杂度为O(h)，h为树的高度，使用Morris遍历算法可以将空间复杂度降低到O(1)。在使用栈时无需判断左子树是是否出处理完毕，并且由于根节点存储在栈中，处理完左子树后可以处理右子树。Morris遍历利用节点中为空的节点来指向根节点。于是有如下遍历框架：

public List traversal(TreeNode root) {
        linkedList list = new linkedList();
        if(root == null)
        	return list;
        TreeNode temp, mostRight;	//temp用来记录当前要处理的节点，mostRight用来记录当前节点的最右子节点
        temp = root; mostRight= null;
        while(temp != null){
        	if(temp.left == null){ //左子树为空则处理右子树
        		temp = temp.right;
        	}else{	//左子树不为空
        		//先判断左子树是否处理过
        		mostRight= temp.left;
        		while(mostRight != null || mostRight != temp){ //找到左子树最右节点
        			mostRight = mostRight.right;
        		}
        		if(mostRight == tmep){	//左子树处理过
        			mostRight = null; //还原二叉树
        		}else{	//左子树没有处理过
        			mostRight = temp; //处理完左子树后，指引回到根节点
        			temp = temp.left; //处理左子树
        		}
        	}
        }
        return list;
    }

很明显上面的算法只能在处理完左子树后回到头节点，在处理完右子树后无法回到头节点。这对先序遍历来说是足够的，但对后序遍历来说，需要在处理完右子树后再处理头节点，因此Morris遍历的后续遍历比较麻烦。下面先给出先序和中序遍历算法：
先序遍历算法

public List traversal(TreeNode root) {
        linkedList list = new linkedList();
        if(root == null)
            return list;
        TreeNode temp, mostRight;	//temp用来记录当前要处理的节点，mostRight用来记录当前节点的最右子节点
        temp = root; mostRight= null;
        while(temp != null){
            if(temp.left == null){ //左子树为空则处理右子树
                list.add(temp.val);	//先处理头节点
                temp = temp.right;
            }else{	//左子树不为空
                //先判断左子树是否处理过
                mostRight= temp.left;
                while(mostRight.right != null && mostRight.right != temp){ //找到左子树最右节点
                    mostRight = mostRight.right;
                }
                if(mostRight.right == null){    //左子树未处理
                    list.add(temp.val);	//处理头节点
                    mostRight.right = temp; //处理完左子树后，指引回到根节点
                    temp = temp.left; //处理左子树
                }else {	//从线索回到头节点时，头节点已经处理过，无需再处理头节点
                    mostRight.right = null; //还原二叉树
                    temp = temp.right;  //处理右子树
                }
            }
        }
        return list;
    }

中序遍历

public List traversal(TreeNode root) {
        linkedList list = new linkedList();
        if(root == null)
            return list;
        TreeNode temp, mostRight;	//temp用来记录当前要处理的节点，mostRight用来记录当前节点的最右子节点
        temp = root; mostRight= null;
        while(temp != null){
            if(temp.left == null){ //左子树为空则处理右子树
                list.add(temp.val);	//先处理头节点
                temp = temp.right;
            }else{	//左子树不为空
                //先判断左子树是否处理过
                mostRight= temp.left;
                while(mostRight.right != null && mostRight.right != temp){ //找到左子树最右节点
                    mostRight = mostRight.right;
                }
                if(mostRight.right == null){    //左子树未处理
                    mostRight.right = temp; //处理完左子树后，指引回到根节点
                    temp = temp.left; //处理左子树
                }else {
                    mostRight.right = null; //还原二叉树
                    list.add(temp.val);	//处理左子树之前处理头节点
                    temp = temp.right;  //处理右子树
                }
            }
        }
        return list;
    }

后续遍历比前序与中序遍历更加麻烦，因为Morris遍历在遍历完右子树节点后无法回到头节点。

后续遍历实际上是从左到右，以上述箭头的方向访问这些节点。我们只要从左到右，每次回溯到根节点时，以箭头方向打印其左子树最右一条边的节点即可。打印最右一条边时，将最右一条边看做一条单链表，反转链表后再依次访问，访问完之后在将链表反转恢复为之前的顺序。于是有以下代码：

public List traversal(TreeNode root) {
        linkedList list = new linkedList();
        if(root == null)
            return list;
        TreeNode temp, mostRight;	//temp用来记录当前要处理的节点，mostRight用来记录当前节点的最右子节点
        temp = root; mostRight= null;
        while(temp != null){
            if(temp.left == null){ //左子树为空则处理右子树
                temp = temp.right;
            }else{	//左子树不为空
                //先判断左子树是否处理过
                mostRight= temp.left;
                while(mostRight.right != null && mostRight.right != temp){ //找到左子树最右节点
                    mostRight = mostRight.right;
                }
                if(mostRight.right == null){    //左子树未处理
                    mostRight.right = temp; //处理完左子树后，指引回到根节点
                    temp = temp.left; //处理左子树
                }else {
                    mostRight.right = null; //还原二叉树
                    printEdege(temp.left, list); 						//逆序输出最右边的一条边
                    temp = temp.right;  //处理右子树
                }
            }
        }
        printEdege(root, list); 
        return list;
    }

public static void printEdege(TreeNode node, linkedList list){
	node = reserve(node);
	while(node != null){
		list.add(node.val);
		node = node.right;
	}
	reserve(node);
}

public static TreeNode reserve(TreeNode node){
	TreeNode pre, temp, next;
	pre = null; temp = node; next= null;
	while(temp != null){
		next = temp.right;
		temp.right = pre;
		pre = temp;
		temp = next;
	}
	return pre;
}