Inorder Traversal

https://practice.geeksforgeeks.org/problems/inorder-traversal/1/

바이너리 트리가 주어졌을때 inorder 순서로 나열하라는 기본적인 코딩 문제 중 하나다.

오랜만이라 inorder가 뭐였는지 까먹어서 예제를 보면서 다시 떠올렸다.

간단하게 설명해서 left child – root – right child 순으로 recursive 하게 <방문 (visit)>하면 된다.

일단 base case 를 설정해주고

def InOrder(root):
    ret=[]
    if root == None:
        return ret

왼쪽 sub-tree 방문해주고

if root.left != None:
    ret.extend(InOrder(root.left))

root 방문해주고

ret.append(root.data)

오른쪽 sub-tree 방문해주고

if root.right != None:
    ret.extend(InOrder(root.right))

결과 값을 돌려주면 된다.

return ret

역시 파이썬은 코딩하기 편하다. 끝

---

전체 코드

def InOrder(root):
    ret=[]
    if root == None:
        return ret
    if root.left != None:
        ret.extend(InOrder(root.left))
    ret.append(root.data)
    if root.right != None:
        ret.extend(InOrder(root.right))
    return ret