[Top Interview Questions] 94. Binary Tree Inorder Traversal

정답)

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
    	# inorder traversal하며 값을 넣을 공간
        res = []

        # res에 넣어줄 nested recursive func
        def inorder(root):
            if not root:
                return    
            inorder(root.left)
            res.append(root.val)
            inorder(root.right)
        
        # recursive func 실행
        inorder(root)
        return res

 

자료참고: NeetCode

문제)

문제출처

 

BInary tree의 루트가 주어졌을 때, inorder traversal한 노드들의 값을 리턴하시오.

 

예시 1)

root = [1, null, 2, 3]

root = [1, null, 2, 3]

output = [1, 3, 2]

 

예시 2)

root = []

output = []

 

예시 3)

root = [1]

output = [1]

 

제한)

트리의 노드들의 갯수는 0~100 사이입니다.

-100 <= node의 val <= 100

풀이)

아... 제가 가장 자신없는 부분이 recursion과 binary tree인데 그 두개를 같이 사용해야되는 문제네요 하하...

원리는 생각나도 실제로 코드 짜는 부분이 너무 어렵습니다 ㅠㅠ

기본원리)

inorder traversal하면서 만나는 노드들의 값을 저장해줄 리스트변수 res를 정의합니다.

 

res에 inorder traversal로 노드들의 val값을 추가해줄 nested recrusive function을 정의합니다.

 

그 recursive function을 실행해 실제 res에 추가해주고 res를 리턴합니다.

inorder traversal)

일단 inorder traversal이 뭔지부터 알아봐야할 것 같습니다.

 

일단 트리 하나를 만들어 주겠습니다.

 

위와 같은 트리를 traverse 하라고 할 때 여러분은 어떻게 하실건가요?

inorder traversal을 따르신다면

 

1. root node의 왼쪽 child node
2. root node
3. root node의 오른쪽 child node

이러한 순서로 traverse하게 됩니다.

그래서 위 그림도 [2, 1, 3]이 되겠죠.

 

아래 그림의 inorder traversal 또한 [4, 2, 5, 1, 3, 6]이 됩니다. 

Inorder Traversal할 때 노드 선형 순서

 

다시 코딩으로)

output으로 정수형 리스트를 리턴해야되기 때문에 inorder traversal하면서 노드의 val값을 추가해줄 리스트 res를 정의해줍니다.

 

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

Base Case)

inorderTraversal() 함수 안에 recursive function을 만들어봅시다.

 

recursive function의 첫번째 스텝은 끝 없는 루프를 멈춰줄 base step을 만드는 것입니다.

 

이 함수에 val값을 지닌 노드가 아닌 Null이 argument로 들어올 경우가 이 recursion을 끝내줄 조건입니다.

그러므로 base case에 위 조건을 충족할 시 루프를 끝내도록 코드를 적어줍시다.

 

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

        def inorder(root):
            if not root:
                return

Recursive Calls)

제가 recursive calls를 하는 부분을 만들 때 처음에는 간단하게 생각해봅니다.

 

실제 코드를 짜기 전에 큰 그림만 보는거죠.

 

저희가 inorder() 함수에서 원하는 것이 무엇인가요?

바로 res 변수에 inorder traversal된 노드들의 값을 넣어주는 것입니다.

 

inorder traversal하게 넣으려면 왼쪽, 루트, 오른쪽 순서대로 res에 추가되어야 합니다.

똑같이 inorder() 함수에 적용시켜봅시다.

 

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

        def inorder(root):
            if not root:
                return
            
            # inorder(root.left)를 했을 때 res에 루트의 왼쪽이 전부
            # inorder traversal하게 res에 추가되었다고 가정
            inorder(root.left)
            
            # 왼쪽을 전부 추가해줬으니 root의 val을 추가
            res.append(root.val)
            
            # inorder(root.right)을 했을 때 res에 루트의 오른쪽 전부
            # inorder traversal하게 res에 추가되었다고 가정
            inorder(root.right)

 

이렇게 적용시킨 후에 논리적으로 접근해보는 것입니다. 

 

inorder() 함수 코드 실행 순서

이런식으로 디버깅 했을 때 논리적으로도 들어맞는다면 recursive function이 완성됩니다.

마지막)

만들어준 inorder() 함수에 주어진 루트 노드 root을 넣어서 실행해줍니다.

 

실행한 후에는 res에 inorder traversal로 노드의 val 값이 추가되었을 것이고 그 res를 리턴하면 됩니다.

 

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

        def inorder(root):
            if not root:
                return
            inorder(root.left)
            res.append(root.val)
            inorder(root.right)
        
        inorder(root)
        return res

디버깅)

root = [1, null, 2, 3]

 

root = [1, null, 2, 3]

res = []

 

inorder(1) -> inorder(Null) -> res.append(1.val) -> inorder(2) -> inorder(3) -> inorder(Null) -> res.append(3.val) -> inorder(Null) -> res.append(2.val) -> inorder(Null)

 

위 코드 실행 순서와 비교하면서 봐주세요

return [1, 3, 2]

 

 

솔직히 이번 설명은 처참하네요 ㅠㅠ. 최대한 알기 쉽게 설명해보려고 했는데 recursion이라는게 저도 다른 주제에 비해서 너무 이해력이 떨어져서... 오늘 공부하면서 얻은 경험치로 다음 설명 때는 더 나아져 보겠습니다. 

 

오늘도 풀이과정에 질문이나 잘못된 부분 있다면 알려주시면 감사하겠습니다 :)