트리 순회 :: Iteration 패턴 정리

가독성도 좋고, 통일성 있게 적용할 수 있는 트리 순회 패턴을 발견했다.
체화하고자 글로 정리한다.

Pre-order

# 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 preorderTraversal(self, root: TreeNode) -> List[int]:
        ans = []
        stack = [(root, False)]
        
        while stack:
            node, hit = stack.pop()
            
            if node:
                if hit:
                    ans.append(node.val)
                else:
                    stack.append((node.right, False))
                    stack.append((node.left, False))
                    stack.append((node, True))
                    
        return ans

In-order

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        ans = []
        stack = [(root, False)]
        
        while stack:
            node, hit = stack.pop()
            
            if node:
                if hit:
                    ans.append(node.val)
                else:
                    stack.append((node.right, False))
                    stack.append((node, True))
                    stack.append((node.left, False))
                    
        return ans

Post-order

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        ans = []
        stack = [(root, False)]
        
        while stack:
            node, hit = stack.pop()
            
            if node:
                if hit:
                    ans.append(node.val)
                else:
                    stack.append((node, True))
                    stack.append((node.right, False))
                    stack.append((node.left, False))
                    
        return ans