LeetCode 108 - Convert Sorted Array to Binary Search Tree

https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/description/?envType=study-plan-v2&envId=top-interview-150

 

오름차순으로 정렬된 nums 배열이 주어졌을 때 이를 height-balanced binary search tree로 변환해라.

 

균형을 맞추는 것이 중요하다.

어떻게 하면 균형을 맞출 수 있을까?

중간값을 부모로 했을 때 균형이 맞게 된다. 배열의 중간값을 현재 서브트리의 루트로 사용하자.

그리고 왼쪽 절반은 왼쪽 서브트리로, 오른쪽 절반은 오른쪽 서브트리로 재귀적으로 처리하면 될 것 같다.

1. 배열의 중간 인덱스를 찾는다.
2. 중간 요소로 새 노드를 만든다.
3. 왼쪽 절반에 대해 재귀를 통해 왼쪽 자식을 설정한다.
4. 오른쪽 절반에 대해 재귀를 통해 오른쪽 자식을 설정한다.

/**
 * 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) {  
        return constructTree(nums, 0, nums.length - 1);
    }

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

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

        return node;
    }

}