Max Howell 参加了谷歌的面试，出题人竟然要求 Max Howell 在白板上作出解答，Max Howell 当然愤怒地拒绝了，回家以后马上在微博上跟我们分享他的吐槽：

Google: % of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.

看来在白板上作出反转二叉树的解答并不容易呢？那么在 ScriptOJ 有上 OJ 系统会不会更方便一些呢？

假如有这样一个二叉树，

        /   \

    /  \    / \

 / \   /   

使用广度优先的原则用数组的表示就是 [, , , , , , , , , , null, null, null, null, null]，二叉树中的空位用 null 表示。

进行反转以后会变成

        /   \

    /  \    /  \

            \   /  \  

使用广度优先的原则用数组的表示就是 [, , , , , , , null, null, null, null, null, , , ]。

请实现函数 invertTree，它接受一个表示二叉树的数组，返回表示这个反转二叉树的数组。

请注意，提交后提示中显示的 ,,,,,, 表示的是 , , , null, null, , 。

package org.rocky.learn.algorithm;

/**

 * Created by admin on 2018/1/10.

 */

public class ConvertArray {

    public static Integer[] convertTree(Integer[] from){

        int length = from.length;

        int height = (int) Math.ceil(log(length, 2));

        int should_size = (int) Math.pow(2, height)-1;

        Integer[] result = new Integer[should_size];

        result = copyArray(from, result);

        int index = 0;

        for(int i=0; i<height; i++){

            int size = (int) Math.pow(2, i);

            result = convertArray(result, index, size);

            index += size;

        }

        return result;

    }

    public static Integer[] copyArray(Integer[] from, Integer[] to){

        for(int i=0; i<Math.min(from.length, to.length); i++){

            to[i] = from[i];

        }

        return to;

    }

    public static double log(double value, double base){

        return Math.log(value)/Math.log(base);

    }

public static Integer[] convertArray(Integer[] from, int beginIndex, int size){

        int length = from.length;

        Integer[] to = new Integer[length];

        for (int i=0; i<length; i++){

            if(i<beginIndex || i>beginIndex+size-1)

                to[i] = from[i];

            else

                to[i] = from[beginIndex + size -1 -(i-beginIndex)];

        }

        return to;

    }

    public static void main(String[] args){

        Integer[] to = convertTree(new Integer[]{1,2,3,4,5,6});

       for(int i=0; i<to.length; i++){

           System.out.print(to[i]==null?"":to[i]);

           if(i<to.length-1)

               System.out.print(",");

       }

    }

}

public static Integer[] convertArray(Integer[] array, int beginIndex, int size){

        int length = array.length;

        if(beginIndex >=0 && beginIndex <= length-1){

            int endIndex = beginIndex+size > length ? length : beginIndex + size;

            for(int i=beginIndex; i<(endIndex+beginIndex)/2; i++){

                int index = endIndex-1-(i-beginIndex);

                Integer temp = array[i];

                array[i] = array[index];

                array[index] = temp;

            }

        }

        return  array;

    }