문제를 이해하고 있다면 바로 풀이를 보면 됨
전체 코드로 바로 넘어가도 됨
마음대로 번역해서 오역이 있을 수 있음

Problem

오름차순으로 정렬된 정수 배열 nums가 주어졌을 때, 높이 균형 이진 탐색 트리로 변환해라.

높이 균형 이진 탐색 트리는 모든 노드에서 두 서브 트리의 깊이 차이가 1을 넘지 않는 이진 트리이다.

Example

#1

Input: nums = [-10, -3, 0, 5, 9]
Output: [0, -3, 9, -10, null, 5]
Explanation: [0, -10, 5, null, -3, null, 9]도 마찬가지로 받아드릴 수 있다.

#2

Input: nums = [1, 3]
Output: [3, 1]
Explanation: [1, null, 3]과 [3, 1] 둘 다 높이 균형 이진 탐색 트리이다.

Constraints

• 1 <= nums.length <= 10^4
• -10^4 <= nums[i] <= 10^4
• nums는 엄격하게 증가하는 순서로 정렬되어있다.

Solved

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        if(nums.length == 0) return null;

        return constructTree(nums, 0, nums.length - 1);
    }

    public TreeNode constructTree(int[] nums, int left, int right){
        if(left > right) return null;

        int mid = (left + right) / 2;
        TreeNode node = new TreeNode(nums[mid]);
        node.left = constructTree(nums, left, mid - 1);
        node.right = constructTree(nums, mid + 1, right);

        return node;
    }
}

주어진 TreeNode 클래스를 사용해서 문제를 해결해야한다.
TreeNode construct메소드에서 nums의 중간 값을 루트로하여 node를 생성하고, 자식 노드를 찾으면서 서브 트리를 완성하면 된다.