《剑指offer》第6题（重建二叉树）的Java实现

自己写的，需要的朋友可以看看。题目内容是根据二叉树前序和中序遍历结果重建二叉树，假设树中元素各不相同。

首先是定义的TreeNode类。

public class TreeNode {
    public int value;
    public TreeNode left,right;
    public TreeNode(int value){
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

下面是实现代码和测试用例。

/**
 * Created by milter on 2017/2/7.
 */
public class Reconstruct_Binary_Tree_offer6 {
    public static TreeNode reconstructBinaryTree(int[]p,int[]m){
        if(p==null||m==null||p.length != m.length||p.length==0)
            return null;
        return recusiveConstruct(p,0,p.length-1,m,0,m.length-1);

    }

    private static TreeNode recusiveConstruct(int[] p, int pStart,int pEnd,
                                              int[] m,int mStart,int mEnd) {
        TreeNode head = new TreeNode(p[pStart]);
        if(pStart == pEnd)
            return head;
        int partition = 0;
        for(int i = mStart; i <= mEnd; i++){
            if(m[i] == p[pStart]){
                partition = i;
                break;
            }
        }
        if(partition - mStart > 0)
            head.left = recusiveConstruct(p,pStart+1,pStart+partition-mStart,
                    m,mStart,partition-1);
        if(mEnd - partition > 0)
            head.right = recusiveConstruct(p,pStart+partition-mStart+1,pEnd,
                    m,partition+1,mEnd);
        return head;
    }

    public static void main(String[] args) {
        int[] p ={1,2,4,7,3,5,6,8};
        int[] m ={4,7,2,1,5,3,8,6};
        TreeNode treeRoot = reconstructBinaryTree(p,m);
        testPreorder(treeRoot);

    }

    private static void testPreorder(TreeNode treeRoot) {
        if(treeRoot == null)
            return;
        System.out.println(treeRoot.value);
        testPreorder(treeRoot.left);
        testPreorder(treeRoot.right);
    }
}