LeetCode算法题-Convert Sorted Array to Binary Search Tree（Java实现）

这是悦乐书的第166次升级，第168篇原创

01 看题和准备

今天详情的是LeetCode算法题中Easy级别的第25题（顺位题号是108）。给定一个数组，其中元素按升序排序，将其转换为高度平衡的二叉搜索树。例如：

给定排序数组：[ -10，-3, 0, 5, 9]

一个可能的答案是：[0，-3, 9，-10，null，5]，它代表以下高度平衡的二叉搜索树：

        0      /   \    -3     9    /     /  -10    5

本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。

02 相关概念

在讨论如何解题前，我们先把题目中的两个概念弄清楚。

二叉搜索树，是一棵空树，或者者是具备下列性质的二叉树：

1）若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值

2）若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值

3）任意节点的左、右子树也分别为二叉搜索树

总结一下就是任意节点的值始终满足 左节点值 < 根节点值 < 右节点值 这个条件。

平衡二叉树，是一颗空树，或者者具备下列性质的二叉树：

1）左子树是一颗二叉平衡树

2）右子树是一颗二叉平衡树

3）左右两个子树的高度差的绝对值不超过1

总结一下就是 |左子树层数-右子树层数| <= 1 。

另外，我们再来理解下二叉树中序遍历这个概念，这对我们解题会有所帮助。

中序遍历，假如二叉树不为空，则会首先遍历左子树，而后访问根节点，最后遍历右子树。

      A    /    \   B      C  / \    / D   E  F

上面的二叉树中序遍历的结果是：DBEAFC 。

03 解题

我们发现那个给出的示例数组，其实就是那个二叉平衡搜索树的中序遍历结果，数组的中间值就是二叉树的根节点，往前就是左子树，往后就是右子树，所以我们可以借助二分法，将数组分为三部分，第一部分从首位到中间位，第二部分是中间位，第三部分是中间位到尾位，利用这三部分分别递归给二叉树设值就可。

public TreeNode sortedArrayToBST(int[] nums) {    return addNode(nums, 0, nums.length-1);}public TreeNode addNode(int[] nums, int left, int right){    if (left > right) {        return null;    }    int mid = (right + left)/2;    TreeNode t = new TreeNode(nums[mid]);    t.left = addNode(nums, left, mid-1);    t.right = addNode(nums, mid+1, right);    return t;}

04 小结

以上就是一律内容，假如大家有什么好的解法思路、建议或者者其余问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！