【算法+資料結構】多種方法實作二叉樹周遊

二叉樹周遊也是面試中經常碰到的題目，這篇文章主要總結一下有關二叉樹周遊的相關問題。

二叉樹結構

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;
        }

    }