엔지니어 게시판
LeetCode 솔루션 분류

[8/10] 108. 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.

height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

 

Example 1:

Input: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: [0,-10,5,null,-3,null,9] is also accepted:

Example 2:

Input: nums = [1,3]
Output: [3,1]
Explanation: [1,null,3] and [3,1] are both height-balanced BSTs.

 

Constraints:

  • 1 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • nums is sorted in a strictly increasing order.
Accepted
804,149
Submissions
1,192,759

관련자료

댓글 3

학부유학생님의 댓글

  • 학부유학생
  • 작성일
Runtime: 128 ms, faster than 52.36% of Python3 online submissions for Convert Sorted Array to Binary Search Tree.
Memory Usage: 15.6 MB, less than 32.22% of Python3 online submissions for Convert Sorted Array to Binary Search Tree.
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        
        def build_tree(arr):
            if not arr: return None
            mid = len(arr)//2
            
            root = TreeNode(arr[mid])
            root.left = build_tree(arr[:mid])
            root.right = build_tree(arr[mid+1:])
            
            return root
        
        return build_tree(nums)

austin님의 댓글

  • austin
  • 작성일
class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        auto make = [](auto self, auto left, auto right) -> TreeNode* {
            if (left == right) return nullptr;
            auto mid = left + distance(left, right) / 2;
            return new TreeNode(*mid, self(self, left, mid), self(self, next(mid), right));            
        };
        return make(make, nums.begin(), nums.end());
    }
};

재민재민님의 댓글

  • 재민재민
  • 작성일
Runtime: 20 ms, faster than 62.77% of C++ online submissions for Convert Sorted Array to Binary Search Tree.
Memory Usage: 21.4 MB, less than 40.73% of C++ online submissions for Convert Sorted Array to Binary Search Tree.
class Solution {
public:
    TreeNode* create_node(vector<int>& nums, int left, int right)
    {
        TreeNode* ans = NULL;
        
        if(left == right)
        {
            ans = new TreeNode(nums[left]);
        }
        else if(left < right)
        {
            int mid = (right + left)/2;
            ans = new TreeNode(nums[mid]);

            ans->left = create_node(nums, left, mid-1);
            ans->right = create_node(nums, mid+1, right);
        }
        
        return ans;
    }
    
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        TreeNode* ans = NULL;
        
        int left = 0;
        int right = nums.size()-1;
        
        ans = create_node(nums, left, right);
        
        return ans;
        
    }
};
전체 240 / 1 페이지
게시글 쓰기
번호
제목
이름

최근글


인기글


새댓글


Stats


  • 현재 접속자 78 명
  • 오늘 방문자 956 명
  • 어제 방문자 829 명
  • 최대 방문자 1,463 명
  • 전체 회원수 379 명
알림 0