108. Convert Sorted Array to Binary Search Tree

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

Convert Sorted Array to Binary Search Tree - LeetCode

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,3] and [3,1] are both a height-balanced BSTs.

 

Constraints:

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums is sorted in a strictly increasing order.

 

Solution

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        if not nums:
            return 0
        
        table = {}
        for num in nums:
            if table.get(num) != None:
                continue
            
            if table.get(num-1) and table.get(num+1):
                left = table[num-1]
                right = table[num+1]
                
                table[num-left] = table[num-left] + right + 1
                table[num+right] = table[num+right] + left + 1                
                table[num] = 0
            elif table.get(num-1) != None:
                temp = table[num-1]
                table[num] = temp + 1
                table[num-temp] = temp + 1
            elif table.get(num+1) != None:
                temp = table[num+1]
                table[num] = temp + 1
                table[num+temp] = temp + 1            
            else:
                table[num] = 1
        
        return max(table.values())

• table key는 리스트의 수를 의미하고, value는 지금까지의 연속된 수의 값을 의미한다.
• 리스트를 보면서 양쪽 모두에 숫자가 있으면, 길이를 계산하여 해당 시퀀스 양 끝에 value를 최신화한다.
• 한쪽에만 수가 있으면 해당 숫자와 반대쪽 끝의 value를 최신화한다.
• 양쪽 모두 수가 없으면 해당 숫자 value에 1을 넣는다.
• 코드가 생각보다 길다.

 

another 1

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        longest_streak = 0
        num_set = set(nums)
        for num in num_set:
            if num - 1 not in num_set:
                current_num = num
                current_streak = 1
                while current_num + 1 in num_set:
                    current_num += 1
                    current_streak += 1
                longest_streak = max(longest_streak, current_streak)
        return longest_streak

• list를 set으로 만들었다.
• set을 사용했기 때문에, 중복된 요소를 고려할 필요가 없다.
• set을 하나씩 보면서, 각 시퀀스의 처음이라면(이전 수가 없을 때) 시퀀스의 길이를 확인한다.
• 추가적인 메모리를 쓰지 않고, 코드가 깔끔해서 좋다.