LeetCode | Binary Tree Traversal

Follow up: Recursive solution is trivial, could you do it iteratively?

재귀(recursive) 방식

• 매번 함수를 호출할 때마다 스택 프레임이 추가되므로, 트리의 높이(height)에 비례하여 추가 공간이 필요
• 따라서 공간 복잡도는 O(h)
• 코드의 간결성이 중요할 때
• 트리가 매우 높은 경우 스택 오버플로우 발생 가능성

반복(iterable) 방식

• 스택이나 큐를 활용해 순회하므로 추가적인 공간이 트리의 크기(노드 수)에 비례하지 X
• 따라서 공간 복잡도는 O(1)
• 메모리 사용량이 중요할 때

트리의 크기와 형태에 따라 방식 선택하기. 두 방식 모두 시간 복잡도는 O(n) 으로 동일하다.

Preorder Traversal 전위 순회

(링크)

현재 노드 -> 왼쪽 노드 -> 오른쪽 노드

recursive

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []

        def traverse(node):
            if not node:
                return

            result.append(node.val)
            traverse(node.left)
            traverse(node.right)

        traverse(root)
        return result

iterable

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        stack, answer = [root], []

        while stack:
            node = stack.pop()

            if node:
                answer.append(node.val)
                if node.right:
                    stack.append(node.right)
                if node.left:
                    stack.append(node.left)

        return answer

Inorder Traversal 중위 순회

(링크)

왼쪽 노드 -> 현재 노드 -> 오른쪽 노드

recursive

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []

        def traverse(node):
            if not node:
                return

            traverse(node.left)
            result.append(node.val)
            traverse(node.right)

        traverse(root)
        return result

iterable

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        stack, answer = [], []
        node = root

        while stack or node:
            while node:
                stack.append(node)
                node = node.left

            node = stack.pop()
            answer.append(node.val)
            node = node.right

        return answer

Postorder Traversal 후위 순회

(링크)

왼쪽 노드 -> 오른쪽 노드 -> 현재 노드

recursive

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []

        def traverse(node):
            if not node:
                return

            traverse(node.left)
            traverse(node.right)
            result.append(node.val)

        traverse(root)
        return result

iterable

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        stack, answer = [(root, False)], []

        while stack:
            node, visited = stack.pop()
            if node:
                if visited:
                    answer.append(node.val)
                else:
                    stack.append((node, True))
                    stack.append((node.right, False))
                    stack.append((node.left, False))

        return answer

Traversal 1줄에 끝내기

노드의 순서만 기억하면 파이썬에서는 1줄로도 전위, 중위, 후위 순회를 재귀 방식으로 구현할 수 있다.

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        # if not root:
        #     return []
        return [root.val] + self.preorderTraversal(root.left) + self.preorderTraversal(root.right) if root else []

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        # if not root:
        #     return []
        return self.inorderTraversal(root.left) + [root.val]  + self.inorderTraversal(root.right) if root else []

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        # if not root:
        #     return []
        return self.postorderTraversal(root.left) +  self.postorderTraversal(root.right) + [root.val] if root else []