23.03.14 Today’s Leetcode

Rank : 95644

10만 돌파

129. Sum Root to Leaf Numbers (medium)

# 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 sumNumbers(self, root: Optional[TreeNode]) -> int:
        ans = 0 

        def dfs(node, value):
            if not node:
                return
            if not node.left and not node.right:
                nonlocal ans
                ans += value * 10 + node.val
                return
            value = value * 10
            value += node.val
            dfs(node.left, value)
            dfs(node.right, value)
        
        dfs(root, 0)
        return ans

988. Smallest String Starting From Leaf (medium)

class Solution:
    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:
        # ab < aba : -1
        def compare(a, b):
            n1, n2 = len(a), len(b)
            n3 = min(n1, n2)
            for i in range(n3):
                if a[i] > b[i]:
                    return 1
                if a[i] < b[i]:
                    return -1

            if n1 == n2:
                return 0
            return -1 if n1 < n2 else 1

        res = []
        
        def dfs(node, his):
            if not node: return 

            if not node.left and not node.right:
                nonlocal res
                temp = [node.val] + his[::-1]
                if not res or compare(temp, res) == -1:
                    res = temp[:]
                return
            
            his.append(node.val)
            dfs(node.right, his)
            his.pop()

            his.append(node.val)
            dfs(node.left, his)
            his.pop()

        dfs(root, [])
        return ''.join([chr(x + 97) for x in res])
        

889. Construct Binary Tree from Preorder and Postorder Traversal (medium)

class Solution:
    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        if not preorder:
            return None
        head_value = preorder[0]
        pre_left, pre_right = [], []
        post_left, post_right = [], []
        n = len(preorder)
        for i in range(n - 1):
            if set(preorder[1:1 + i]) == set(postorder[:i]):
                pre_left, pre_right = preorder[1:1 + i], preorder[1 + i:]
                post_left, post_right = postorder[:i], postorder[i:-1]
        
        node = TreeNode(head_value)
        node.left = self.constructFromPrePost(pre_left, post_left)
        node.right = self.constructFromPrePost(pre_right, post_right)
        return node

2497. Maximum Star Sum of a Graph (medium)

class Solution:
    def maxStarSum(self, vals: List[int], edges: List[List[int]], k: int) -> int:
        tree = defaultdict(list)
        for a, b in edges:
            tree[a].append(b)
            tree[b].append(a)
        
        def calculate(node):
            res = vals[node]
            arr = []
            for neigh in tree[node]:
                heappush(arr, -vals[neigh])
            temp = vals[node]
            for i in range(min(k, len(arr))):
                tar = -heappop(arr)
                # print(tar)
                temp += tar
                res = max(res, temp)
            return res
        
        ans = -math.inf        
        for i in range(len(vals)):
            ans = max(ans, calculate(i))
        return ans