545. Boundary of Binary Tree (Tree, Depth-First Search, Binary Tree)

링크 - https://leetcode.com/problems/boundary-of-binary-tree/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Medium

Intuition

이 문제는 get_left_boundary, get_right_boundary, get_leaves를 각각 계산해주는 메서드를 만들어주는게 좋다. dfs방식을 사용하여 문제를 풀 수 있기 때문에 방법만 잘 설정해주면 더 깔끔한 코드가 된다.

Code

# 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 boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []

        def get_left_boundary(node):
            if not node or (not node.left and not node.right):
                return

            boundary.append(node.val)
            if node.left:
                get_left_boundary(node.left)
            elif node.right:
                get_left_boundary(node.right)
            return

        def get_right_boundary(node):
            if not node or (not node.left and not node.right):
                return

            if node.right:
                get_right_boundary(node.right)
            elif node.left:
                get_right_boundary(node.left)
            boundary.append(node.val)

        def get_leaves(node):
            if not node:
                return

            if not node.left and not node.right and node is not root:
                boundary.append(node.val)
            else:
                get_leaves(node.left)
                get_leaves(node.right)

        boundary = [root.val]
        get_left_boundary(root.left)
        get_leaves(root)
        get_right_boundary(root.right)
        return boundary

Complexity

Time Complexity: O(n) DFS이므로 모든 노드 탐색

Space Complexity: O(n) DFS