import org.apache.commons.lang.StringUtils;
import org.springframework.util.ObjectUtils;

/**
 * @author lxq
 */
public class TreeNode {
    /**
     * 节点值
     */
    private String value;

    /**
     * 左子树
     */
    private TreeNode left;

    /**
     * 右子树
     */
    private TreeNode right;

    public TreeNode(String value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }

    private String getValue() {
        return value;
    }

    private void setValue(String value) {
        this.value = value;
    }

    private TreeNode getLeft() {
        return left;
    }

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

    private TreeNode getRight() {
        return right;
    }

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

    public static void main(String[] args) {
        String preString = "12473568";
        String middleString = "47215386";

        TreeNode node = buildBinaryTree(preString, middleString);

        if (!ObjectUtils.isEmpty(node)) {
            postOrder(node);
        }

        System.out.println();

        if (!ObjectUtils.isEmpty(node)) {
            buildMirrorBinaryTree(node);
            postOrder(node);
        }

    }

    /**
     * 重建二叉树
     *
     * @param preString
     * @param middleString
     * @return
     */
    private static TreeNode buildBinaryTree(String preString, String middleString) {
        //1.1 前序或者中序为空，直接范围null
        if (StringUtils.isBlank(preString) || StringUtils.isBlank(middleString)) {
            System.out.println("前序和中序字符串为空");
            return null;
        }

        //1.2 长度不同直接范围null
        if (preString.length() != middleString.length()) {
            System.out.println("前序和中序字符串长度不相等");
            return null;
        }

        //2.获取Tree的根节点
        String root = preString.substring(0, 1);
        TreeNode node = new TreeNode(root);

        //3.获取在中序节点中的位置
        int rootLeftLength = middleString.indexOf(root);

        //4.1.如果处在最左出，则左子树没有
        if (rootLeftLength == 0) {
            node.left = null;
            //4.2 递归构建左子树
        } else {
            node.left = buildBinaryTree(preString.substring(1, rootLeftLength + 1), middleString.substring(0, rootLeftLength));
        }

        //5.1如果处在最右侧，则右子树没有
        if (rootLeftLength == middleString.length() - 1) {
            node.right = null;
        } else {
            //5.2 递归构建右子树
            node.right = buildBinaryTree(preString.substring(rootLeftLength + 1), middleString.substring(rootLeftLength + 1));
        }

        return node;
    }

    /**
     * 二叉树后续遍历
     *
     * @param subTree
     */
    private static void postOrder(TreeNode subTree) {
        if (subTree != null) {
            postOrder(subTree.left);
            postOrder(subTree.right);
            System.out.print(subTree.getValue());
        }
    }

    /**
     * 构建镜像二叉树
     *
     * @param node
     */
    private static void buildMirrorBinaryTree(TreeNode node) {
        //1.二叉树为空
        if (ObjectUtils.isEmpty(node)) {
            return;
        }

        //2.单节点二叉树
        if (node.getLeft() == null && node.getRight() == null) {
            return;
        }

        //3.交换左右孩子
        TreeNode temp = node.getLeft();
        node.setLeft(node.getRight());
        node.setRight(temp);

        //4.递归进行镜像设置
        if (node.getLeft() != null) {
            buildMirrorBinaryTree(node.getLeft());
        }

        if (node.getRight() != null) {
            buildMirrorBinaryTree(node.getRight());
        }
    }
}