LeetCode 솔루션

[8/10] 108. Convert Sorted Array to Binary Search Tree

학부유학생 쪽지보내기 메일보내기 자기소개 아이디로 검색 전체게시물 작성
작성일 2022.08.09 21:33

11,256 조회
3 댓글
0 추천
0 비추천
목록 게시글 쓰기

108. Convert Sorted Array to Binary Search Tree

Easy

7280385Add to ListShare

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

A 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

#Amazon, #Microsoft, #Apple, #Adobe, #Yahoo, #Oracle

링크

https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/ 2487 회 연결

익명
작성일 2022.08.09 21:34

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)

익명
작성일 2022.08.10 01:12

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());
    }
};

익명
작성일 2022.08.16 22:16

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;
        
    }
};

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.
[code=c]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;
        
    }
};[/code]