【算法+数据结构】多种方法实现二叉树遍历

二叉树遍历也是面试中经常碰到的题目，这篇文章主要总结一下有关二叉树遍历的相关问题。

二叉树结构

public static class Node{
 		//左子节点
        public Node left;
        //右子节点
        public Node right;
        public int value;

        public Node(int v){
            value = v;
        }
    }
           

二叉树的遍历

• 层次遍历 ：主要借助队列先进先出来实现

• 深度遍历 ：三种顺序

  先序(头，左，右),

  中序(左、头、右),

  后序(左、右、头)

  三种深度遍历皆可以通过递归，非递归(借助栈来实现)，morris方式来实现。其中三种方式的时间复杂度均为O(N), 递归和非递归的空间复杂度为O(H)，而morris方法的空间复杂度为O(1)

层次遍历

主要借助队列先进先出来实现

public void level(Node head){

        if(head == null){
            return;
        }
        Queue<Node> queue = new LinkedList<>();
        //将头节点放入队列中
        queue.add(head);
        //当队列不为空时，每次弹出一个节点，弹出就打印
        while (!queue.isEmpty()){
            Node cur = queue.poll();
            System.out.print(cur.value);
			//依次判断弹出的做孩子和右孩子是否为空，
			//不为空加入队列中
            if(cur.left != null){
                queue.add(cur.left);
            }

            if(cur.right != null){
                queue.add(cur.right);
            }
        }
    }
           

深度遍历

递归方式

递归序：

二叉树递归遍历存在递归序，二叉树中的每一个节点在递归序中
都会通过该节点三次，第一次通过就打印该节点称为先序遍历
第二次经过该节点就打印称为中序遍历，第三次经过该节点就
打印称为后序遍历
           

//递归序
    public void f(Node head){
        if(head == null){
            return;
        }
        // 先序 打印head.value
        f(head.left);
        //中序 打印head.value
        f(head.right);
        //后序 打印head.value
    }
           

非递归方式

非递归方式的深度遍历都是借助栈来实现的，都遵循一个原则：
弹出就打印 (后序利用两个栈的方式是弹出就入栈)
           

先序

主要借助栈来实现头，左，右的顺序打印
           

public void pre(Node head){
        if(head == null){
            return;
        }
        Stack<Node> stack = new Stack<>();
        //将头节点压入栈中
        stack.push(head);
		//栈不为空时，弹出一个节点就打印
        while (!stack.isEmpty()){
            head = stack.pop();
            System.out.print(head.value);
			
			//依次判断右孩子，左孩子，不为空则加入栈
            if(head.right != null){
                stack.push(head.right);
            }

            if(head.left != null){
                stack.push(head.left);
            }
        }

    }
           

中序

借助栈来实现 左，头，右的打印顺序。
本质是依次将二叉树的左子树加入栈中。
           

public void in(Node head){

        if(head == null){
            return;
        }
        Stack<Node> stack = new Stack<>();
		//初始条件，head不为null或者站不为空，则继续
        while (head != null || !stack.isEmpty()){
			//如果head不为空，则加入栈中，并来到左子树
            if(head != null){
                stack.push(head);
                head = head.left;
            }else{
            	//直到head为null，就一直弹出就打印，
            	//之后来到右子树
                head = stack.pop();
                System.out.print(head.value);
                head = head.right;
            }
        }

    }

           

后序

方式一： 借助两个栈来实现，基于先序排序，将先序排序稍作修改在入栈时，先左孩子，再右孩子，同时弹出节点时，不打印，而是直接放入另一个栈中，直到第一个栈为空时，依次打印第二个栈的值即可。

public void pos1(Node head){
        if(head == null){
            return;
        }

        Stack<Node> s1 = new Stack<>();
        Stack<Node> s2 = new Stack<>();

        s1.push(head);

        while (!s1.isEmpty()){
            head = s1.pop();
            s2.push(head);
            System.out.print(head.value);

            if(head.left != null){
                s1.push(head.left);
            }

            if(head.right != null){
                s1.push(head.right);
            }

        }

        while (!s2.isEmpty()){
            System.out.print(s2.pop() + " ");
        }

    }
           

方式二:

借助栈和两个变量来实现左，右，头的顺序打印

//整个流程都是先处理左孩子，再处理右孩子，再处理头节点
//那么在栈中为什么顺序没有反过来，因为这里用的是peek，并没有poll
public  void pos2(Node h){

        if( h == null){
            return;
        }

        Stack<Node> stack = new Stack<>();
        stack.push(h);
		//c为当前遍历的节点
        Node c = null;
        //这里的h代表上次打印的节点，
        //开始默认为head(其实随便指定一个不相干的值即可)
        while (!stack.isEmpty()){
        	//取头顶的节点作为当前节点，这里并不弹出
            c = stack.peek();
			
			//如果c有左孩子，
			//并且c节点的左右孩子都没打印，则直接压入左孩子
            if(c.left != null 
		            && h != c.left 
		            && h != c.right){
		            
                stack.push(c.left);
           //如果c有右孩子，且右孩子没有打印，则直接压入右孩子
            }else if( c.right != null 
            		&& h != c.right){
            		
                stack.push(c.right);
                
            }else {
            	//两个孩子都处理完了，该处理头节点了，弹出并打印
                System.out.print(stack.pop()+" ");
                h = c;
            }
        }
    }

           

morris方式

利用有限几个变量实现二叉树的深度遍历。

在morris遍历中，如果一个节点有左孩子，那么morris遍历就会经过该节点两次(一次，是左孩子的最右节点指向null，第二次是左孩子的最右节点指向cur)。其余节点只会经过一次。

morris遍历的流程：

1、cur节点来到head节点
2、如果cur节点无左树，则cur = cur.left
3、如果cur节点有左树：
	a、找到cur左树上的最右节点mostRight,如果
		mostRight节点为null,那么 让
		mostRight.right = cur, cur = cur.left;
	b、如果mostRight.right == cur,那么让
		mostRight.right = null, cur = cur.right;
           

public static void morris(Node head){
        if(head == null){
            return;
        }

        Node cur = head;
        Node mostRight = null;

        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{
                    //来到这里说明节点 mostRight.right == cur,是第二次来到当前节点了
                    mostRight.right = null;
                }
            }

            cur = cur.right;
        }

    }