ReConstructBinaryTree.java

package com.vamdt.fox.fox.of;

import java.util.HashMap;
import java.util.Map;

/**
 * pre arr + in arr => tree
 * in arr + post arr => tree
 * pre arr + post arr => tree
 */
public class ReConstructBinaryTree {

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    public static void main(String[] args) {
        int[] pre = new int[] {1,2,4,7,3,5,6,8};
        int[] in = new int[] {4,7,2,1,5,3,8,6};
        int[] post = new int[] {7,4,2,5,8,6,3,1};
        ReConstructBinaryTree test = new ReConstructBinaryTree();
//        TreeNode head = test.reConstructBinaryTreeByInAndPost(post, in);
        TreeNode head = test.reConstructBinaryTreeByPreAndPost(new int[]{1,2,4,5,3,6,7}, new int[]{4,5,2,6,7,3,1});
        printTreePre(head);
        System.out.println();
        printTreeIn(head);
        System.out.println();
        printTreePost(head);
        System.out.println();
    }

    public static void printTreePre(TreeNode node) {
        if (node == null) {
            return;
        }
        System.out.print(node.val);
        System.out.print(' ');
        printTreePre(node.left);
        printTreePre(node.right);
    }

    public static void printTreeIn(TreeNode node) {
        if (node == null) {
            return;
        }
        printTreeIn(node.left);
        System.out.print(node.val);
        System.out.print(' ');
        printTreeIn(node.right);
    }
    public static void printTreePost(TreeNode node) {
        if (node == null) {
            return;
        }
        printTreePost(node.left);
        printTreePost(node.right);
        System.out.print(node.val);
        System.out.print(' ');
    }

    // 先序和中序构造二叉树
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if (pre == null || in == null) {
            return null;
        }
        Map<Integer, Integer> helpMap = new HashMap<>();
        for (int i = 0; i < in.length; i++) {
            helpMap.put(in[i], i);
        }
        return reConstructBinaryTree(pre, helpMap, 0, pre.length - 1, 0, in.length - 1);
    }

    private TreeNode reConstructBinaryTree(int[] pre, Map<Integer, Integer> helpMap, int preLeft, int preRight, int inLeft, int inRight) {
        // 子树大小为负，子树为空
        if (preLeft > preRight) {
            return null;
        }
        TreeNode treeNode = new TreeNode(pre[preLeft]);
        int inIndex = helpMap.get(treeNode.val);
        // 中序索引 - 先序索引 = 左子树大小
        int leftTreeSize = inIndex - inLeft;
        treeNode.left = reConstructBinaryTree(pre, helpMap, preLeft + 1, preLeft + leftTreeSize, inLeft, inIndex -1);
        treeNode.right = reConstructBinaryTree(pre, helpMap, preLeft + leftTreeSize + 1, preRight, inIndex + 1, inRight);
        return treeNode;
    }


    // 中序和后序构造二叉树
    public TreeNode reConstructBinaryTreeByInAndPost(int [] post, int [] in) {
        if (post == null || in == null) {
            return null;
        }
        Map<Integer, Integer> helpMap = new HashMap<>();
        for (int i = 0; i < in.length; i++) {
            helpMap.put(in[i], i);
        }
        return reConstructBinaryTreeByInAndPost(post, helpMap, 0, post.length - 1, 0, in.length - 1);
    }

    private TreeNode reConstructBinaryTreeByInAndPost(int[] post, Map<Integer, Integer> helpMap, int postLeft, int postRight, int inLeft, int inRight) {
        // 子树大小为负，子树为空
        if (postLeft > postRight) {
            return null;
        }
        TreeNode treeNode = new TreeNode(post[postRight]);
        int inIndex = helpMap.get(treeNode.val);
        // 中序索引 - 先序索引 = 左子树大小
        int leftTreeSize = inIndex - inLeft;
        treeNode.left = reConstructBinaryTreeByInAndPost(post, helpMap, postLeft, postLeft + leftTreeSize - 1, inLeft, inIndex -1);
        treeNode.right = reConstructBinaryTreeByInAndPost(post, helpMap, postLeft + leftTreeSize, postRight - 1, inIndex + 1, inRight);
        return treeNode;
    }

    // 先序和后序构造二叉树,只有在非叶节点都有左孩子和右孩子的情况下，才可以构造成整颗树
    // 以下不能准确构造出二叉树， 左右两颗树的先序都为[1,2],后序都为[2,1]
    //   1   1
    //  /    \
    // 2      2
    //
    public TreeNode reConstructBinaryTreeByPreAndPost(int [] pre, int [] post) {
        if (pre == null || post == null) {
            return null;
        }
        Map<Integer, Integer> helpMap = new HashMap<>();
        for (int i = 0; i < post.length; i++) {
            helpMap.put(post[i], i);
        }
        return reConstructBinaryTreeByPreAndPost(pre, helpMap, 0, pre.length - 1, 0, post.length - 1);
    }

    private TreeNode reConstructBinaryTreeByPreAndPost(int[] pre, Map<Integer, Integer> helpMap, int preLeft, int preRight, int postLeft, int postRight) {
        // 左 == 右，遇到叶节点，返回
        TreeNode treeNode = new TreeNode(pre[preLeft]);
        if (preLeft == preRight) {
            return treeNode;
        }
        int leftTreeNodePostIndex = helpMap.get(pre[++preLeft]);
        int leftTreeSize = leftTreeNodePostIndex - postLeft;
        treeNode.left = reConstructBinaryTreeByPreAndPost(pre, helpMap, preLeft, preLeft + leftTreeSize, postLeft, leftTreeNodePostIndex);
        treeNode.right = reConstructBinaryTreeByPreAndPost(pre, helpMap, preLeft + leftTreeSize + 1, preRight, leftTreeNodePostIndex + 1, postRight -1);
        return treeNode;
    }


}