二叉树遍历

import java.util.Stack;

/**
 * @ author:mian
 * @ DATA:2018/5/7 16:10
 */
class Node{
    public int value;
    public Node left;
    public Node right;
    public Node(int data){
        this.value = data;
    }
}
public class 二叉树遍历 {
    //前序遍历-递归
    public static void preOrderRecur(Node head){
        if(head==null){
            return;
        }
        System.out.println(head.value+" ");
        preOrderRecur(head.left);
        preOrderRecur(head.right);
    }
    //中序遍历
    public static void inOrderRecur(Node head){
        if(head==null){
            return;
        }
        inOrderRecur(head.left);
        System.out.println(head.value+"");
        inOrderRecur(head.right);
    }
    //后序遍历
    public static void posOrderRecur(Node head){
        if(head==null){
            return;
        }
        posOrderRecur(head.left);
        posOrderRecur(head.right);
        System.out.println(head.value+" ");
    }
    //前序非递归
    public static void preOrderUnRecur(Node head){
        System.out.println("pre-order:");
        if(head!=null){
            Stack<Node> stack = new Stack<Node>();
            stack.add(head);
            while(!stack.isEmpty()){
                head=stack.pop();
                System.out.println(head.value+" ");
                if(head.right!=null){
                    stack.push(head.right);
                }
                if(head.left!=null){
                    stack.push(head.left);
                }
            }
        }
        System.out.println();
    }
    //中序非递归
    public static void inOrderUnRecur(Node head){
        System.out.println("in-order");
        if(head!=null){
            Stack<Node> stack=new Stack<Node>();
            if(head!=null){
                while(!stack.isEmpty()||head!=null){
                    if(head!=null){
                        stack.push(head);
                        head = head.left;
                    }else{
                        head = stack.pop();
                        System.out.println(head.value+" ");
                        head = head.right;
                    }
                }
            }
        }
        System.out.println();
    }
}

前序，中序，后序任选两个重构二叉树

import java.util.HashMap;

/**
 * @ author:mian
 * @ DATA:2018/5/7 16:51
 */
public class 遍历序列重构二叉树 {
    //先序和中序重构二叉树
    public static Node preInToTree(int[] pre,int[] in){
        if(pre==null||in==null){
            return null;
        }
        HashMap<Integer,Integer> map = new HashMap<Integer, Integer>();
        for(int i=0;i<in.length;i++){
            map.put(in[i],i);
        }
        return preIn(pre,0,pre.length-1,in,0,in.length-1,map);
    }
    public static Node preIn(int[] p,int pi,int pj,int[] n,int ni,int nj,HashMap<Integer,Integer> map){
        if(pi>pj){
            return null;
        }
        Node head = new Node(p[pi]);
        int index = map.get(p[pi]);
        head.left = preIn(p,pi+1,pi+index-ni,n,ni,index-1,map);
        head.right =preIn(p,pi+index-ni,pj,n,index+1,nj,map);
        return head;
    }

    //中序和后序
    public static Node inPosToTree(int[] in,int[] pos){
        if(in==null||pos==null){
            return null;
        }
        HashMap<Integer,Integer> map = new HashMap<Integer, Integer>();
        for(int i=0;i<in.length;i++){
            map.put(in[i],i);
        }
        return inPos(in,0,in.length-1,pos,0,pos.length-1,map);
    }
    public static Node inPos(int[] n,int ni,int nj,int[] s,int si,int sj,HashMap<Integer,Integer> map){
        if(si>sj){
            return null;
        }
        Node head=new Node(s[sj]);
        int index = map.get(s[sj]);
        head.left = inPos(n,ni,index-1,s,si,si+index-ni-1,map);
        head.right=inPos(n,index+1,nj,s,si+index-ni,sj-1,map);
        return head;
    }
}