[leetcode] 3-6회차

독서를 시작할 계절이 왔다.

 

https://leetcode.com/problems/binary-tree-right-side-view/?envType=study-plan-v2&envId=top-interview-150

 

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def bfs(self, root, ans, depth):
        if not root:
            return ans
        if len(ans) < depth:
            ans.append(root.val)
        ans = self.bfs(root.right, ans, depth+1)
        ans = self.bfs(root.left, ans, depth+1)
        return ans

    
    def rightSideView(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: List[int]
        """
        ans = []
        if not root:
            return ans
        ans = self.bfs(root, ans, 1)

        return ans

 

 

 

https://leetcode.com/problems/average-of-levels-in-binary-tree/description/?envType=study-plan-v2&envId=top-interview-150

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def bfs(self, root, sum_cnt, depth):
        if not root:
            return sum_cnt
        if depth >= len(sum_cnt):
            sum_cnt.append([root.val, 1])
        else:
            sum_cnt[depth][0] += root.val
            sum_cnt[depth][1] += 1
        
        sum_cnt = self.bfs(root.left, sum_cnt, depth+1)
        sum_cnt = self.bfs(root.right, sum_cnt, depth+1)

        return sum_cnt


    def averageOfLevels(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: List[float]
        """
        sum_cnt = [] # it will be saved the value like [(sum, cnt)]

        if not root:
            return root
        sum_cnt = self.bfs(root, sum_cnt, 0)
        
        ans = []
        for nums, cnt in sum_cnt:
            print(nums, cnt, (float(nums)/cnt))
            ans.append((float(nums)/cnt))
        return ans

코드가 복잡하다. 

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def averageOfLevels(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: List[float]
        """
        q, ans = [root], []

        while len(q):
            qlen, row = len(q), 0
            for i in range(qlen):
                curr = q.pop(0)
                row += curr.val
                if curr.left: q.append(curr.left)
                if curr.right: q.append(curr.right)
            
            ans.append(float(row)/qlen)

        return ans

많은 추천수를 받은 답안인데, 확실히 깔끔하다. qlen 을 통해서 같은 행에 있는 값을 셀 수 있도록 코드를 작성했는데 상당히 압축되고 편해보인다. 다음에 이런 방식을 사용해봐야지 :)