Leetcode :: Binary Tree order Traversal

Problem

Given the root of a binary tree, return the inorder traversal of its nodes' values.

Guess

• Binary Tree 중위 순회를 구현하는 문제다.
• Recursion, Iteration 으로 각각 구현해보자.

Sol 1. Reursion

# 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 inorderTraversal(self, root: TreeNode) -> List[int]:
        ans = []
        self.helper(root, ans)
        return ans
    
    def helper(self, root, ans):
        if not root:
            return ans
        
        self.helper(root.left, ans)
        ans.append(root.val)
        self.helper(root.right, ans)

Sol 2. Iteration

# 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 inorderTraversal(self, root: TreeNode) -> List[int]:
        ans = []
        stack = []
        curr = root
        
        while curr or stack:
            while curr:
                stack.append(curr)
                curr = curr.left
                
            curr = stack.pop()
            ans.append(curr.val)
            curr = curr.right
            
        return ans