[Mock] Random 18

easy 두 문제~

---

226. Invert Binary Tree

Given the root of a binary tree, invert the tree, and return its root.

My Answer 1: Accepted (Runtime: 80 ms - 5.60% / Memory Usage: 14 MB - 90.14%)

# 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 invertTree(self, root: TreeNode) -> TreeNode:
        def func(root):
            if root is None:
                return
            
            func(root.left)
            func(root.right)
            
            tmp = root.left
            root.left = root.right
            root.right = tmp
        
        func(root)
        
        return root

그냥 pre-order 로 순회하면서 left 와 right 를 swap

Solution 1: Accepted (Runtime: 56 ms - 5.60% / Memory Usage: 14.3 MB - 10.41%)

# 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 invertTree(self, root: TreeNode) -> TreeNode:
        stack = [root]
        while stack:
            node = stack.pop()
            if node:
                node.left, node.right = node.right, node.left
                stack += node.left, node.right
        return root

반복문을 이용한 방법, stack 사용

left, right swap 후, stack 에 left, right 넣기

---

690. Employee Importance

You have a data structure of employee information, which includes the employee's unique id, their importance value, and their direct subordinates' id.

You are given an array of employees employees where:

• employees[i].id is the ID of the ith employee.
• employees[i].importance is the importance value of the ith employee.
• employees[i].subordinates is a list of the IDs of the subordinates of the ith employee.

Given an integer id that represents the ID of an employee, return the total importance value of this employee and all their subordinates.

My Answer 1: Accepted (Runtime: 160 ms - 15.51% / Memory Usage: 15.4 MB - 65.42%)

"""
# Definition for Employee.
class Employee:
    def __init__(self, id: int, importance: int, subordinates: List[int]):
        self.id = id
        self.importance = importance
        self.subordinates = subordinates
"""

class Solution:
    def getImportance(self, employees: List['Employee'], id: int) -> int:
        dic = {}
        for i in range(len(employees)):
            dic[employees[i].id] = [employees[i].importance, employees[i].subordinates]
        
        def func(did):
            self.ans += did[0]
            
            for i in did[1]:
                func(dic[i])
            
        self.ans = 0
        func(dic[id])
        
        return self.ans

employees 는 0 인덱스에 1 값이 고정된 게 아니므로...
dic 에 id 별로 importance 와 subordinates 저장

그러고 재귀 돌려서 주어진 id 값과 연결된 employee 들의 importance 를 ans 에 저장

근데 제출할 때마다 런타임이 달라지는 듯...^^

Solution 1: Accepted (Runtime: 148 ms - 94.88% / Memory Usage: 15.4 MB - 84.76%)

"""
# Definition for Employee.
class Employee:
    def __init__(self, id: int, importance: int, subordinates: List[int]):
        self.id = id
        self.importance = importance
        self.subordinates = subordinates
"""

class Solution:
    def getImportance(self, employees: List['Employee'], id: int) -> int:
        emap = {e.id: e for e in employees}
        def dfs(eid):
            employee = emap[eid]
            return (employee.importance +
                    sum(dfs(eid) for eid in employee.subordinates))
        return dfs(id)

루션이도 map 을 만들어서 재귀 돌림