47, 48, 49. Binary Tree Traversal(inorder, preorder, postorder)

문제

이진 트리를 순회한 결과를 반환하시오.

 

1. Recursive

1) Inorder

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        def inorder(current_node):
            if not current_node:
                return []
            left_nodes = inorder(current_node.left)
            right_nodes = inorder(current_node.right)
            
            return left_nodes + [current_node.val] + right_nodes
        
        return inorder(root)

2) Preorder

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        def postorder(root_node):
            if not root_node:
                return []
            
            left_nodes = preorder(root_node.left) if root_node.left else []
            right_nodes = preorder(root_node.right) if root_node.right else []
            
            return [root_node.val] + left_nodes + right_nodes
        
        return postorder(root)

3) Postorder

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

 

2. Iterative

1) inorder

def inorderTraversel(self, root):
  result = []
  stack = []

  while stack or root:
    # 루트의 좌측 노드, 좌측 노드의 좌측 노드..를 모두 stack에 저장
    if root:
      stack.append(root)
      root = root.left
    
    # 좌측 노드의 끝까지 가서 더 넣을 것이 없는 경우
    # stack에 들어있는 노드 꺼내서 우측 노드 탐색
    else:
      temp = stack.pop()
      result.append(temp.val)
      root = temp.right

  return result

 

2) preorder

def preorderTraversal(self, root):
    result = []
    stack = []

    while stack or root:
        if root:
            # 루트가 있으면 result, stack에 넣기
            stack.append(root)
            result.append(root.val)
            # 루트의 좌측 노드를 루트로 만들기
            root = root.left
        else:
            # 좌측 노드의 끝까지 가서 더 넣을 것이 없는 경우
            # stack에 들어있는 노드 꺼내서 우측 노드 탐색
            root = stack.pop()
            root = root.right

    return result

 

3) postorder

https://leetcode.com/problems/binary-tree-postorder-traversal/discuss/45786/Python-recursive-and-iterative-solutions.

def postorderTraversal(self, root):
    result = []
    stack = [root]
    
    while stack:
        # 1) 스택에서 pop하기
        node = stack.pop()
        
        if node:
            # 2) result에 pop한 결과 넣기
            # 3) stack에 pop한 노드의 왼쪽, 오른쪽 노드 추가
            result.append(node.val)
            stack.append(node.left)
            stack.append(node.right)
    
    # 4) result 리스트 뒤집기
    return result[::-1]