重构二叉树

原文链接：http://blog.csdn.net/qq_22329521/article/details/52948072
二叉树的遍历常见方式

enter image description here

• 前序遍历，先访问跟节点，在访问子结点，最后访问右子结点顺序是abdefgc
• 中序遍历，先访问左子结点，再访问根结点，最后访问右子结点debgfac
• 后序遍历，先访问左子结点，在访问右子结点，最后访问更结点edgfbca
• 宽度优先遍历，先访问树的第一层结点，再访问树的第二层结点，一致到访问到最下面一层结点，同一层结点，从左到右一次遍历abcdfeg

重构二叉树

输入二叉树的前序遍历和中序遍历都不含重复数字，重建该二叉树
思路：已知前序找根结点，然后判断跟结点在中序输出中的位置，根节点左边的就是左子树，右边就是右子树，递归查找

 public static void test4() {
        int[] frontOrder = {1, 2, 4, 7, 3, 5, 6, 8};
        int[] inOrder = {4, 7, 2, 1, 5, 3, 8, 6};
        BinaryTreeNode root = BinaryTree(frontOrder, inOrder);
        printPostOrder(root);
    }

    public static void printPostOrder(BinaryTreeNode root) {
        if (root != null) {
            printPostOrder(root.getLeft());
            printPostOrder(root.getRight());
            System.out.println(root.getValue());
        }
    }

    public static BinaryTreeNode BinaryTree(int[] frontOrder, int[] inOrder) {
        //根据前序结点获取当前的跟结点
        BinaryTreeNode root = new BinaryTreeNode(frontOrder[0]);
        root.setLeft(null);
        root.setRight(null);
        int leftLength = 0;
        //从中序结点中获取前序结点这个数所在的位置，因为中序结点中左侧是左字数，右侧是右字数
        for (int i = 0; i < inOrder.length; i++) {
            if (inOrder[i] == root.getValue()) {
                break;
            } else {
                leftLength++;
            }
        }
        //获取右子树的个数
        int rightLength = inOrder.length - leftLength - 1;
        if (leftLength > 0) {
            //再次初始化左侧的左子树
            int[] leftFrontOrder = new int[leftLength];
            int[] leftInorder = new int[leftLength];
            for (int j = 0; j < leftLength; j++) {
                //因为第一个被取走了
                leftFrontOrder[j] = frontOrder[j + 1];
                leftInorder[j] = inOrder[j];
            }
            BinaryTreeNode leftRoot = BinaryTree(leftFrontOrder, leftInorder);
            root.setLeft(leftRoot);
        }
        //再次初始化右侧的右子树
        if (rightLength > 0) {
            int[] rightFrontOrder = new int[rightLength];
            int[] rightInorder = new int[rightLength];
            for (int k = 0; k < rightLength; k++) {
                rightFrontOrder[k] = frontOrder[k + 1 + leftLength];
                rightInorder[k] = inOrder[k + 1 + leftLength];
            }
            BinaryTreeNode rightRoot = BinaryTree(rightFrontOrder, rightInorder);
            root.setRight(rightRoot);
        }
        return root;
    }

public class BinaryTreeNode {
    private int value;
    private BinaryTreeNode left;
    private BinaryTreeNode right;
    public BinaryTreeNode(int value){
        this.value = value;
    }
    public BinaryTreeNode(int value,BinaryTreeNode left,BinaryTreeNode right){
        this.value = value;
        this.left = left;
        this.right = right;
    }
    public int getValue( ){
        return this.value;
    }
    public void setValue(BinaryTreeNode node){
        this.value = value;
    }
    public void  setLeft(BinaryTreeNode node){
        this.left = node;
    }
    public void  setRight(BinaryTreeNode node){
        this.right = node;
    }
    public BinaryTreeNode getLeft( ){
        return this.left;
    }
    public BinaryTreeNode getRight( ){
        return this.right;
    }
}