题解 | 将升序数组转化为平衡二叉搜索树

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    public TreeNode sortedArrayToBST (int[] num) {
        if (num == null || num.length == 0) {
            return null;
        }
        // 传入数组的起始索引和结束索引
        return buildTree(num, 0, num.length - 1);
    }

    private TreeNode buildTree(int[] num, int left, int right) {
        // 递归的终止条件：如果左边界大于右边界，说明没有元素了，返回 null
        if (left > right) {
            return null;
        }

        // 使用 left + (right - left) / 2 是为了防止 left + right 导致的整型溢出
        int mid = left + (right - left) / 2;

        // 将中间位置的数字作为当前树的根节点
        TreeNode root = new TreeNode(num[mid]);

        // 递归构建左子树，范围是中间节点左边的所有元素
        root.left = buildTree(num, left, mid - 1);

        // 递归构建右子树，范围是中间节点右边的所有元素
        root.right = buildTree(num, mid + 1, right);

        //  返回构建好的根节点
        return root;
    }
}