有序数组转二分查找树的分治算法

所谓分治算法：就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解

下面展示一个有序数组转二分查找树的实现

首先是景点的二叉树结构

/**
 * 二叉树的典型结构实现
 * 
 * @author kangye
 * @param <T>
 */
public class BinaryNode<T> {

    private final T data;
    private BinaryNode<T> left;
    private BinaryNode<T> right;

    public BinaryNode(T data) {
        this.data = data;
    }

    public T getData() {
        return data;
    }

    public BinaryNode<T> getLeft() {
        return left;
    }

    public void setLeft(BinaryNode<T> left) {
        this.left = left;
    }

    public BinaryNode<T> getRight() {
        return right;
    }

    public void setRight(BinaryNode<T> right) {
        this.right = right;
    }

    public boolean hasLeft() {
        return left != null;
    }

    public boolean hasRight() {
        return right != null;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o)
            return true;
        if (!(o instanceof BinaryNode))
            return false;

        BinaryNode that = (BinaryNode) o;

        if (!data.equals(that.data))
            return false;
        if (left != null ? !left.equals(that.left) : that.left != null)
            return false;
        if (right != null ? !right.equals(that.right) : that.right != null)
            return false;

        return true;
    }

    @Override
    public int hashCode() {
        int result = data.hashCode();
        result = 31 * result + (left != null ? left.hashCode() : 0);
        result = 31 * result + (right != null ? right.hashCode() : 0);
        return result;
    }

    @Override
    public String toString() {
        return "BinaryNode{" + "data=" + data + '}';
    }
}

基本算法

/**
 * 将有序数组转换成一颗二叉查找树
 * 
 * @author kangye
 */
public class SortedArrayToBST {

    /**
     * 验证
     * 
     * @author kangye
     * @param sortedArray
     * @return
     */
    public BinaryNode<Integer> transform(Integer[] sortedArray) {
        if (sortedArray == null || sortedArray.length == 0) {
            throw new IllegalArgumentException("You can't use a null or empty array.");
        }
        return transformToBST(sortedArray, 0, sortedArray.length - 1);
    }

    /**
     * 分治算法 把一个复杂的问题分成:两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解
     * 
     * @author kangye
     * @param sortedArray  有序数组， 在分支中仍然保留完整数组
     * @param bottom       起始位置
     * @param top          结束为止
     * @return
     */
    private static BinaryNode<Integer> transformToBST(Integer[] sortedArray, int bottom, int top) {
        int center = (top + bottom) / 2;
        if (sortedArray.length == 1) {
            return new BinaryNode<Integer>(sortedArray[0]);
        } else if (bottom > top) {
            return null;
        } else {
            BinaryNode node = new BinaryNode<Integer>(sortedArray[center]);
            node.setLeft(transformToBST(sortedArray, bottom, center - 1));
            node.setRight(transformToBST(sortedArray, center + 1, top));
            return node;
        }
    }

}

 照例最后是单元测试

/**
 * @author kangye.
 */
public class SortedArrayToBSTTest {

    private SortedArrayToBST sortedArrayToBST;

    @Before
    public void setUp() {
        sortedArrayToBST = new SortedArrayToBST();
    }

    @Test(expected = IllegalArgumentException.class)
    public void shouldNotAcceptNullArrays() {
        sortedArrayToBST.transform(null);
    }

    @Test(expected = IllegalArgumentException.class)
    public void shouldNotAcceptAnEmptyArray() {
        Integer[] emptyArray = new Integer[0];
        sortedArrayToBST.transform(emptyArray);
    }

    @Test
    public void shouldReturnJustOneNodeIfTheArrayContainsJustOneElement() {
        Integer[] array = { 1 };

        BinaryNode<Integer> result = sortedArrayToBST.transform(array);

        assertEquals(new Integer(1), result.getData());
    }
}

一个有意思的问题，转换成Python是个什么样子？