有序数组转换成二叉查找树 (Java 实现)

[二叉查找树](https://zh.wikipedia.org/wiki/% E4% BA%8C% E5%85%83% E6%90%9C% E5% B0%8B% E6% A8% B9) 也称为排序二叉树或有序二叉树。将二叉查找树中序遍历就能得到一个有序数组。所以，有序数组转换成二叉查找树是中序遍历的逆操作。将数组中下标为中数的元素作为根节点，利用递归实现转换。以下是实现代码：

public class Demo {

    public static void main(String[] args) {

        int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13};

        printBST(sortedArrayToBST(array));

    }

    public static TreeNode sortedArrayToBST(int[] array) {
        if (array == null || array.length == 0)
            return null;

        return recursionBST(array, 0, array.length - 1);
    }

    private static TreeNode recursionBST(int[] array, int start, int end) {
        // 返回左子节点为空，结束此次递归
        if (start > end)
            return null;

        // 返回没有左右子节点的节点，结束此次递归
        if (start == end)
            return new TreeNode(array[start]);

        int mid = start + (end - start) / 2;// 取中数
        TreeNode root = new TreeNode(array[mid]);// 根节点
        root.left = recursionBST(array, start, mid - 1);// 尾递归遍历
        root.right = recursionBST(array, mid + 1, end);// 尾递归遍历

        return root;// 依次结束最里层递归
    }

    // 输出树，此处为举例的笨方法，暂时没想到更好的解决方法，如果不是完全二叉树，此方法会有 NullPointerException。
    public static void printBST(TreeNode root) {
        System.out.println(root.val);
        System.out.println(root.left.val + " " + root.right.val);
        System.out.println(root.left.left.val + " " + root.left.right.val + " " + root.right.left.val + " " + root.right.right.val);
        System.out.println(root.left.left.left.val + " " + root.left.left.right.val + " " + root.left.right.left.val + " " + root.left.right.right.val + " " + root.right.left.left.val + " " + root.right.left.right.val + " " + root.right.right.left.val + " " + root.right.right.right.val);
    }
}

class TreeNode {
    int val;//value

    TreeNode left;// 左子树

    TreeNode right;// 右子树

    // 构造方法
    TreeNode(int x) {
        val = x;
    }
}

以上只是其中一种转换方法，此方法所转换的二叉查找树不是完全二叉树时，只会缺左叶子节点。

参考网址

Leetcode Convert Sorted Array to Binary Search Tree 有序数组转换成二叉搜索树 BST