【数据结构和算法】递归方式解决

递归方式解决

题中说了要转换为一棵高度平衡的二叉搜索树，并且数组又是排过序的，这就好办了。

我们可以使用递归的方式，每次取数组中间的值比如m作为当前节点，m前面的值都是比他小的，作为他左子树的结点值。m后面的值都是比他大的，作为他右子树的节点值，示例中一个可能的结果是。

代码如下

public TreeNode sortedArrayToBST(int[] num) {
    //边界条件判断
    if (num.length == 0)
        return null;
    return sortedArrayToBST(num, 0, num.length - 1);
}

//start表示数组开始的位置，end表示的结束的位置
public TreeNode sortedArrayToBST(int[] num, int start, int end) {
    if (start > end)
        return null;
    //中间节点
    int mid = (start + end+1) >> 1;
    //取中间值作为当前节点
    TreeNode root = new TreeNode(num[mid]);
    //然后递归的方式，中间值之前的是当前节点左子树的所有节点
    root.left = sortedArrayToBST(num, start, mid - 1);
    //中间值之后的是当前节点的右子树的所有节点
    root.right = sortedArrayToBST(num, mid + 1, end);
    return root;
}

截止到目前我在公众号“数据结构和算法”中已经写了500多道算法题，其中部分已经整理成了pdf文档，目前总共有1000多页（并且还会不断的增加），大家可以免费下载
下载链接：https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码：6666

如果觉得有用就给个赞吧，还可以关注我的《牛客博客》查看更多的详细题解