有序数组转换成二叉查找树 (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

DeppWang wechat
个人公众号