[코테 풀이] Convert Sorted Array to Binary Search Tree

Q_108) Convert Sorted Array to Binary Search Tree

출처 : https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/

Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.

/**
 * 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 bst(nums, 0, nums.length - 1);
    }
    public TreeNode bst(int nums[], int l, int r) {
        if (l > r) return null;
        int mid = l + (r-l) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = bst(nums, l, mid - 1);
        root.right = bst(nums, mid + 1, r);
        return root;
    }
}

🙈 풀이 참조한 문제
ex) nums = {-10, -3, 0, 5, 9} 일 경우

1) 첫번째 bst 호출
bst({-10, -3, 0, 5, 9}, 0, 4)
l = 0, r = 4, mid = 2
TreeNode root = new TreeNode(0)
root.left = bst({-10, -3, 0, 5, 9}, 0, 1) (left subtree)
root.right = bst({-10, -3, 0, 5, 9}, 3, 4) (right subtree)

2) 1번에서의 root.left
bst({-10, -3, 0, 5, 9}, 0, 1)
l = 0, r = 1, mid = 0
TreeNode root = new TreeNode(-10)
root.left = bst({-10, -3, 0, 5, 9}, 0, -1) (return null)
root.right = bst({-10, -3, 0, 5, 9}, 1, 1) (right subtree)

3) 2번에서의 root.right
bst({-10, -3, 0, 5, 9}, 1, 1)
l = 1, r = 1, mid = 1
TreeNode root = new TreeNode(-3)
root.left = bst({-10, -3, 0, 5, 9}, 1, 0) (return null)
root.right = bst({-10, -3, 0, 5, 9}, 2, 1) (return null)

4) 1번에서의 root.right
bst({-10, -3, 0, 5, 9}, 3, 4)
l = 3, r = 4, mid = 3
TreeNode root = new TreeNode(5)
root.left = bst({-10, -3, 0, 5, 9}, 3, 2) (return null)
root.right = bst({-10, -3, 0, 5, 9}, 4, 4) (right subtree)

5) 4번에서의 root.right
bst({-10, -3, 0, 5, 9}, 4, 4)
l = 4, r = 4, mid = 4
TreeNode root = new TreeNode(9)
root.left = bst({-10, -3, 0, 5, 9}, 4, 3) (return null)
root.right = bst({-10, -3, 0, 5, 9}, 5, 4) (return null)

🥸 Balanced Binary Tree? (균형 이진 트리)

• BST에서도 left subtree와 right subtree의 height 차이가 1보다 크지 않은 트리

🥸 Balanced BST? (균형 이진 탐색 트리)

• Node의 삽입 / 삭제시, 균형을 유지하도록 하는 트리
  ex) AVL Tree, Red-Black Tree