23.02.25 Today’s Leetcode

106. Construct Binary Tree from Inorder and Postorder Traversal (medium)

예전에 풀었던 Inorder, Preorder과 비슷한 방식으로 해결.

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        if not inorder:
            return None
        if len(postorder) == 1:
            return TreeNode(postorder[0])
        node = TreeNode(postorder[-1])
        index = inorder.index(postorder[-1])
        node.left = self.buildTree(inorder[:index], postorder[:index])
        node.right = self.buildTree(inorder[index + 1:], postorder[index:-1])
        return node

108. Convert Sorted Array to Binary Search Tree (easy)

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        n = len(nums)
        if n == 1:
            return TreeNode(nums[0])
        mid = n // 2
        node = TreeNode(nums[mid])
        if mid < n:
            node.left = self.sortedArrayToBST(nums[:mid])
        if mid + 1 < n:
            node.right = self.sortedArrayToBST(nums[mid + 1:])
        return node

110. Balanced Binary Tree (easy)

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True

        res = True
        def height(node):
            if not node:
                return 0
            l = height(node.left)
            r = height(node.right)
            if abs(l - r) > 1:
                nonlocal res
                res = False
            return max(l, r) + 1

        height(root)
        return res
        # return 2 ** (h - 1) <= c and c < 2 ** h
        

114. Flatten Binary Tree to Linked List (medium)

class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        if not root:
            return None
        
        self.flatten(root.left)
        self.flatten(root.right)
        r, l = root.right, root.left
        root.right = l
        cur, prev = root.right, root
        while cur:
            prev.left = None
            prev = cur
            cur = cur.right
        prev.right = r

119. Pascal’s Triangle II (easy)

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        res = []
        for i in range(rowIndex + 1):
            res += [1]
            # reversed for loop
            for j in range(len(res) - 2, 0, -1):
                res[j] = res[j] + res[j - 1]
        return res

125. Valid Palindrome (easy)

class Solution:
    def isPalindrome(self, s: str) -> bool:
        s = s.lower()
        t = ''
        for w in s:
            if w.isalpha() or w.isnumeric():
                t += w
        # print(t)
        return t == t[::-1]

137. Single Number II (medium)

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        counter = Counter(nums)
        for key in counter.keys():
            if counter[key] == 1:
                return key
        return -1