树的前序/后序+中序构建二叉树

例题：

image.png

image.png

public interface ConstructBTreeThroughAnyTwoTraverse {
    /**
     * 通过前序遍历和中序遍历构造二叉树
     * @param preStr 前序遍历结果
     * @param inStr 中序遍历结果
     * @return
     */
    TreeNode createBTreeThoughPreOrderAndInOrder(String preStr,String inStr);

    /**
     * 通过后序遍历和中序遍历构造二叉树
     * @param postStr 后序遍历结果
     * @param inStr 中序遍历结果
     * @return
     */
    TreeNode createBTreeThoughPostOrderAndInOrder(String postStr,String inStr);
}

public class ConstructBTreeThroughAnyTwoTraverseImpl
        implements ConstructBTreeThroughAnyTwoTraverse {
    private TreeNode root;
    private int preIndex=0;
    private int currPostIndex;
    /**
     * 通过前序遍历和中序遍历构造二叉树
     * @param preStr 前序遍历结果
     * @param inStr 中序遍历结果
     * @return
     */
    @Override
    public TreeNode createBTreeThoughPreOrderAndInOrder(String preStr, String inStr) {
        if(preStr.length() ==0 || inStr.length()==0)
            return null;
        root=create(preStr,inStr,0,inStr.length()-1);
        return root;
    }

    private TreeNode create(String preStr, String inStr, int start, int end) {
        //与创建平衡二叉搜索树代码类似
        if(start>end || preIndex>preStr.length()-1)
            return null;
        //根节点的值
        int rootVal=preStr.charAt(preIndex);
        preIndex++;
        //根节点在中序中的位置
        int rootValIndex=inStr.indexOf(rootVal);
        TreeNode temp=new TreeNode(rootVal);
        temp.setLeft(create(preStr,inStr,start,rootValIndex-1));
        temp.setRight(create(preStr,inStr,rootValIndex+1,end));
        return temp;
    }

    /**
     * 获得指定位置根的值
     * @param preStr
     * @param i
     * @return
     */
    private char getRootVal(String preStr, int i) {
        return preStr.charAt(i);
    }


    /**
     * 通过后序遍历和中序遍历构造二叉树
     * @param postStr 后序遍历结果
     * @param inStr 中序遍历结果
     * @return
     */
    @Override
    public TreeNode createBTreeThoughPostOrderAndInOrder(String postStr, String inStr) {
        //与创建平衡二叉搜索树代码类似
        if(postStr.length() ==0 || inStr.length()==0)
            return null;
        currPostIndex=postStr.length()-1;
        root=createPostInOrder(postStr,inStr,0,inStr.length()-1);
        return root;
    }

    private TreeNode createPostInOrder(String postStr, String inStr, int start, int end) {
        if(start>end || currPostIndex<0)
            return null;
        //当前根节点的值
        int currentRootVal=postStr.charAt(currPostIndex--);
        //根节点在中序结果的位置
        int currentRootValIndex=inStr.indexOf(currentRootVal);
        TreeNode temp=new TreeNode(currentRootVal);
        /**
         * 和createBTreeThoughPreOrderAndInOrder类似
         * createBTreeThoughPreOrderAndInOrder是根左右建树；
         * 模仿createBTreeThoughPreOrderAndInOrder
         * 需要注意的是：一定要根 右 左 建树！！
         * 因为后序遍历是左 右 根
         * 原因：因为从后序遍历结果中获得根节点是倒序的，即后序遍历是左右根
         * 当倒着获取根的时候，因此就要采取根右左方式建树
         */
        temp.setRight(createPostInOrder(postStr,inStr,currentRootValIndex+1,end));
        temp.setLeft(createPostInOrder(postStr,inStr,start,currentRootValIndex-1));
        return temp;
    }

//BTreeOpration 实现：https://www.jianshu.com/writer#/notebooks/45706548/notes/69590811/preview
    public static void main(String[] args){
        ContsrcutBTreeThroughAnyTwoTraverseImpl c=new ContsrcutBTreeThroughAnyTwoTraverseImpl();
        TreeNode pre=c.createBTreeThoughPreOrderAndInOrder("ABECDFGHIJ","EBCDAFHIGJ");
        TreeNode post=c.createBTreeThoughPostOrderAndInOrder("EDCBIHJGFA","EBCDAFHIGJ");
        BTreeOpration b=new BTreeOpration();
        //输出的是int，但是结果正确
        b.inOrderTraverseBTree(pre);
        System.out.println();

        b.inOrderTraverseBTree(post);
        //System.out.println(node);
    }
}

/**
 * 二叉树结点
 */
public class TreeNode {
    private TreeNode left;
    private TreeNode right;
    private Integer data;
    /**
     * 构造节点
     * @param data
     */
    public TreeNode(int data) {
        this.data = data;
        this.left=null;
        this.right=null;
    }
    public TreeNode(){}

    public void setLeft(TreeNode left) {
        this.left = left;
    }

    public void setRight(TreeNode right) {
        this.right = right;
    }

    public Integer getData() {
        return data;
    }

    public TreeNode getLeft() {
        return left;
    }

    public TreeNode getRight() {
        return right;
    }

    public void setData(Integer data) {
        this.data = data;
    }

    @Override
    public String toString() {
        return "TreeNode{" +
                "left=" + left +
                ", right=" + right +
                ", data=" + data +
                '}';
    }
}