Algorithm

94. Binary Tree Inorder Traversal

Doljae 2021. 4. 5. 14:09
 

Binary Tree Inorder Traversal - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

1. DFS를 이용한 Inorder 구현

from typing import *


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

        def move(cur):
            if cur.left:
                move(cur.left)
            answer.append(cur.val)
            if cur.right:
                move(cur.right)

        move(root)
        return answer

 

2. Stack을 이용한 Inorder 구현

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        answer = []
        stack = []
        cur = root
        while cur or stack:
            while cur:
                stack.append(cur)
                cur = cur.left
            cur = stack.pop()
            answer.append(cur.val)
            cur = cur.right
        return answer