二叉树的遍历

前序遍历：根节点->左子树->右子树

中序遍历：左子树->根节点->右子树

后序遍历：左子树->右子树->根节点

求下面树的三种遍历：

前序遍历：abdefgc

中序遍历：debgfac

后序遍历：edgfbca

已知前序、中序遍历，重构二叉树

前序遍历的第一个值就是根节点，然后再中序遍历中找到这个值，那么这个值的左边部分即为当前二叉树的左子树部分前序遍历结果，这个值的右边部分即为当前二叉树的右子树部分前序遍历结果。

如上图：前序a为根节点，再看中序里面的a，由于中序是（左根右），所以a的左边debgf为左子树，右边c为右子树

代码如下：

/**
 * Created by wuchao on 17-3-28.
 */
public class Class01 {
    public static void main(String[] args){
        int[] pre = {1,2,4,7,3,5,6,8};
        int[] in = {4,7,2,1,5,3,8,6};
        TreeNode tree  = reConstructBinaryTree(pre,in);
        System.out.println(preSort(tree));
        System.out.println(inSort(tree));

    }
    //根据前序和中序排列构造二叉树
    public static TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        int root = pre[0];//pre的第一个元素肯定是这两个数组的根根节点

        //下面将pre的所有元素前移，目的是每次执行该函数，都可以依次获取pre的元素，而不需要添加索引
        for(int i=0;i<pre.length-1;i++){
            pre[i]=pre[i+1];
        }

        if(in.length==1){
            return new TreeNode(root);
        }

        //System.out.println(root);
        int index=-1;//表示根节点在in中的位置，in数组中，根节点左侧是左子树，右侧是右子树
        //下面查找根节点在in的位置
        for(int i=0;i<in.length;i++){
            if(root == in[i]){
                index =i;
                break;
            }
        }

        TreeNode tree = new TreeNode(root);
        if(index>0){
            int[] inTmp = new int[index];
            for(int i=0;i<index;i++){
                inTmp[i]=in[i];
            }
            tree.left=reConstructBinaryTree(pre,inTmp);
        }

        if(index<in.length-1){
            int[] inTmp = new int[in.length-1-index];
            for(int i=index+1;i<in.length;i++){
                inTmp[i-index-1]=in[i];
            }
            tree.right=reConstructBinaryTree(pre,inTmp);
        }
        return tree;
    }
    //前序排列
    public static String preSort(TreeNode tree){
        if(tree ==null) return "";
        String res="";
        res=res+tree.val;
        if(tree.left!=null){
            res = res+preSort(tree.left);
        }
        if(tree.right!=null){
            res = res+preSort(tree.right);
        }
        return res;
    }
    //中序排列
    public static String inSort(TreeNode tree){
        if(tree ==null) return "";
        String res="";
        if(tree.left!=null){
            res=res+inSort(tree.left);
        }
        res=res+tree.val;
        if(tree.right!=null){
            res=res+inSort(tree.right);
        }
        return res;
    }
    //后序排列
    public static String postSort(TreeNode tree){
        if(tree ==null) return "";
        String res="";
        if(tree.left!=null){
            res = res+preSort(tree.left);
        }
        if(tree.right!=null){
            res = res+preSort(tree.right);
        }
        res=res+tree.val;
        return res;
    }
    //打印数组
    public static void printArray(int[] array){
        String s="[";
        for(int i=0;i<array.length;i++){
            s=s+" "+array[i];
        }
        s=s+"]";
        System.out.println(s);
    }
    static class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }
}

已知前序、中序遍历，求后序遍历

如上图：前序a为根节点，再看中序里面的a，由于中序是（左根右），所以a的左边debgf为左子树，右边c为右子树

所以递归调用左子树：左子树的前序遍历中序遍历为：bdefg、debgf

再递归调用右子树：c、c

递归的过程：

1 确定根,确定左子树，确定右子树。

2 在左子树中递归。

3 在右子树中递归。

4 打印当前根。

已知中序、后序，求前序遍历

后序遍历最后一个结点即为根结点

递归的过程：

1 确定根,确定左子树，确定右子树。

2 在左子树中递归。

3 在右子树中递归。

4 打印当前根。