二分探索木の中間順走査は昇順シーケンスを生成します。問題で与えられた配列は昇順でソートされているため、この配列は二分探索木の中間順走査シーケンスであることが保証されます。

1. 二分探索木の中間順走査が与えられた場合、二分探索木を一意に決定できるか？

答えは否定的です。もし二分探索木の高さバランスを要求しない場合、任意の数字を根ノードとして選択できるため、複数の異なる二分探索木が存在しうります。

2. 高さバランスという制約条件を追加した場合、二分探索木を一意に決定できるか？

この場合も答えは依然として否定的です。

直感的に考えると、中央の数字を二分探索木の根ノードとして選択することで、左右の部分木に割り当てられる数字の数が同じか、あるいは1つしか差がなくなり、木がバランスを保つことができます。

配列の長さが奇数の場合、根ノードの選択は一意に決まります。しかし、配列の長さが偶数の場合、中央位置の左側の数字を根ノードに選ぶか、中央位置の右側の数字を根ノードに選ぶかの2つの選択肢があります。異なる数字を根ノードとして選ぶことで、作成される平衡二分探索木も異なります。

平衡二分探索木の根ノードが決定されると、残りの数字はそれぞれ平衡二分探索木の左部分木と右部分木に配置されます。左部分木と右部分木もまた平衡二分探索木であるため、再帰的な方法で平衡二分探索木を作成できます。

これは直感的な考え方ですが、この方法で木が「平衡」であることが保証される理由については、「LeetCode 1382. 二分探索木を平衡にする」という問題を参照できます。両問題の構築方法は完全に同一であり、この方法の正しさは1382問題の公式解答で証明されています。

再帰の基本ケースは、平衡二分探索木に数字が含まれない場合であり、このとき平衡二分探索木は空になります。

与えられた中間順走査シーケンスの配列において、各部分木に含まれる数字は配列内で連続していることが保証されます。そのため、配列のインデックス範囲を使って部分木に含まれる数字を特定できます。インデックス範囲を[left, right]と記述します。中間順走査シーケンス全体に対しては、インデックス範囲はleft=0からright=nums.length-1です。left > rightの場合、平衡二分探索木は空になります。

1. 方法一：常に中央位置の左側の数字を根ノードとして選択する

中央位置の左側の数字を根ノードとして選択する場合、根ノードのインデックスはmid=(left+right)/2（ここでの除法は整数除法）となります。

class SortedArrayToBSTConverter {
    public TreeNode convertToBST(int[] sortedArray) {
        return buildBalancedTree(sortedArray, 0, sortedArray.length - 1);
    }

    private TreeNode buildBalancedTree(int[] array, int leftIndex, int rightIndex) {
        if (leftIndex > rightIndex) {
            return null;
        }

        // 常に中央位置の左側の数字を根ノードとして選択
        int midIndex = (leftIndex + rightIndex) / 2;

        TreeNode rootNode = new TreeNode(array[midIndex]);
        rootNode.left = buildBalancedTree(array, leftIndex, midIndex - 1);
        rootNode.right = buildBalancedTree(array, midIndex + 1, rightIndex);
        return rootNode;
    }
}

複雑度分析：

時間計算量：O(n)、ここでnは配列の長さです。各数字は一度だけアクセスされます。

空間計算量：O(log n)、ここでnは配列の長さです。空間計算量は戻り値を考慮しないため、主に再帰スタックの深さによって決まります。再帰スタックの深さはO(log n)です。

2. 方法二：常に中央位置の右側の数字を根ノードとして選択する

中央位置の右側の数字を根ノードとして選択する場合、根ノードのインデックスはmid=(left+right+1)/2（ここでの除法は整数除法）となります。

class BalancedBSTCreator {
    public TreeNode createBalancedBST(int[] nums) {
        return constructTree(nums, 0, nums.length - 1);
    }

    private TreeNode constructTree(int[] values, int start, int end) {
        if (start > end) {
            return null;
        }

        // 常に中央位置の右側の数字を根ノードとして選択
        int middle = (start + end + 1) / 2;

        TreeNode root = new TreeNode(values[middle]);
        root.left = constructTree(values, start, middle - 1);
        root.right = constructTree(values, middle + 1, end);
        return root;
    }
}

複雑度分析：

時間計算量：O(n)、ここでnは配列の長さです。各数字は一度だけアクセスされます。

空間計算量：O(log n)、ここでnは配列の長さです。空間計算量は戻り値を考慮しないため、主に再帰スタックの深さによって決まります。再帰スタックの深さはO(log n)です。

3. 方法三：任意の中央位置の数字を根ノードとして選択する

任意の中央位置の数字を根ノードとして選択する場合、根ノードのインデックスはmid=(left+right)/2とmid=(left+right+1)/2のいずれかをランダムに選択します（ここでの除法は整数除法）。

class RandomizedBSTBuilder {
    private java.util.Random randomizer = new java.util.Random();

    public TreeNode buildBalancedBST(int[] inputArray) {
        return generateTree(inputArray, 0, inputArray.length - 1);
    }

    private TreeNode generateTree(int[] array, int leftBound, int rightBound) {
        if (leftBound > rightBound) {
            return null;
        }

        // 任意の中央位置の数字を根ノードとして選択
        int midIndex = (leftBound + rightBound + randomizer.nextInt(2)) / 2;

        TreeNode treeRoot = new TreeNode(array[midIndex]);
        treeRoot.left = generateTree(array, leftBound, midIndex - 1);
        treeRoot.right = generateTree(array, midIndex + 1, rightBound);
        return treeRoot;
    }
}

複雑度分析：

時間計算量：O(n)、ここでnは配列の長さです。各数字は一度だけアクセスされます。

空間計算量：O(log n)、ここでnは配列の長さです。空間計算量は戻り値を考慮しないため、主に再帰スタックの深さによって決まります。再帰スタックの深さはO(log n)です。