LeetCode算法题-Convert Sorted Array to Binary Search Tree(Java实现)

时间:2022-01-15 05:12:34

这是悦乐书的第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 小结

以上就是全部内容,如果大家有什么好的解法思路、建议或者其他问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!