每天做一道算法题,循序渐进,按算法分类刷题。坚持下去,看能坚持多久,也看最终能有多大成效。
将有序数组转换为二叉搜索树
将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。
本题中,一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。
示例:
<code>给定有序数组: [-10,-3,0,5,9], 一个可能的答案是:[0,-3,9,-10,null,5],它可以表示下面这个高度平衡二叉搜索树: 0 / \ -3 9 / / -10 5/<code>
解决方案
根据平衡二叉树左右两个子树的高度差的绝对值不超过 1的性质可以确认中间节点是根节点。
因此首先获取中间节点作为根节点,两边的节点作为左子树和右子树。然后递归生成左子树和右子树。
实现代码
参考衔接
https://blog.csdn.net/sgbfblog/article/details/7786698