Leet code #94 Binary Tree Inorder Traverse (DFS, BFS)

문제. 다음과 같은 Binary Tree가 주어졌을 때,  노드 값들의 inorder traversal 를 반환하는  코드를 짜라

# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

 

---

Discussion 섹션의 Andvary님의 그림을 보고 좀 이해가 갔는데요. preorder/inorder/postorder/bfs이던 이런 Binary tree와 관련된 노드를 순회하는 문제에서는 어떤 순서대로 돌아가는지 구간을 나누는게 포인트였습니다

 

예를 들어, 아래 그림에서 1,2,3,4,5가 가는 방향을 보면 preorder은 노드 > 왼쪽 다 돌고 > 오른쪽으로 이동하고 

inorder은 아래쪽부터 왼 > 노드 > 오를 반복, postorder은 왼 >오 > 노드를 반복하는데요

 

출처: leetcode, andvary

 

문제에서는 Inorder 구문을 짜라고 했으므로 왼 > 노드 > 오의 반복을 이해한채로

공유된 대표 답안 몇가지를 분석해봤습니다

def inorderTraversal(self, root):
    ans = []
    stack = []
    
    while stack or root:
        if root:
            stack.append(root)
            root = root.left
        else:
            tmpNode = stack.pop()
            ans.append(tmpNode.val)
            root = tmpNode.right
        
    return ans

위 답안은 우선 while 구문을 실행해놓고 다음 단계를 반복합니다

(밑에 숨김 되어 있는 사이트에 좀 더 자세히 설명되어 있습니다.)

 

1) 비어있는 stack list를 만듭니다

2) 현재 노드 값을 stack에 push한 뒤, 현재 노드를 왼쪽 노드로 업데이트합니다.

3) 만약 현재 노드값이 null이고 stack이 비어있으면

        3.1 stack의 가장 마지막에 있는 값을 pop합니다

         3.2 pop한 아이템을 저장하고 현재 노드 값을 right로 업데이트 합니다

4) 현재 노드가 null이고 stack이 비면 반복문을 끝냅니다 

 

이 방법은 재귀문을 쓰지 않고 iterative method를 사용해서 왼쪽을 다 돌고 이후에 오른쪽을 돌고 stack이나 root값이 모두 비었을 때 끝내는 방식인데요. 간단히 순환 과정을 상상해보면 위에서 아래로 왼쪽 노드를 담는 stack을 만들고, 왼쪽을 다 돌고난 이후에는 pop을 이용해서 위로 타고 올라가면서 오른쪽 노드를 stack에 다시 추가하고, 오른쪽 노드가 root와 stack이 모두 null값이 되는 마지막까지 다 돌고나서 끝내는 코드인거죠!  

참고 웹사이트:

https://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion/

실행시간, 메모리 사용량 : 60ms, 13.8MB

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:return []
        res = []
        res+=self.inorderTraversal(root.left)
        res.append(root.val)
        res+=self.inorderTraversal(root.right)
        return res

두번째 답안은 왼>노드>오 방식이 좀 더 가시적으로 드러난 코드인데요.

res 라는 비어 있는 list에 += 방식으로 left의 노드를 추가하고, 이후에 root.val, root.right를 추가했습니다

다른 코드와 달리, res =[ ] 값을 디폴트로 반환하도록 해서 root가 비어있을 경우에도 [ ]가 반환되도록 예외처리를 한게 인상적이었어요

실행시간, 메모리 사용량 : 53ms, 13.9MB

 def inorderTraversal(self, root):
        return self.inorderTraversal(root.left)+[root.val]+self.inorderTraversal(root.right) if root else []

세번째는 사실상 위에 있는 코드를 좀 더 직관적이고 간단명료하게 표현한건데요, 이해도 쉽고 inorder traversal의 원리를 가장 잘 표현한 코드라고 생각됩니다!

실행시간, 메모리 사용량 : 40ms, 13.8MB

 

 

위 3가지 방법을 고려해봤을 때 마지막 방법이 가장 실행시간이 짧고 효과적인 코드로 보이네요

문제가 나왔을 때, 알면 접근이 가능하지만 모르면 헤멜 수도 있는 DFS의 탐색방법을 기억해두는게 좋을 것 같습니다 ><

 

 

**Binary Tree Traversal 관련 youtube 참고 영상도 공유드립니다

https://www.youtube.com/watch?v=gtca5ZDy7iU