리트코드 145. Binary Tree Postorder Traversal

26 Nov 2022 in Algorithm

이진 트리의 순회(postorder traversal) 리스트를 반환하시오!

Tree 문제… 🎋

문제

145. Binary Tree Postorder Traversal 문제 링크

이진 트리의 순회(postorder traversal) 해보아라!

# Example 1:
Input: root = [1,null,2,3]
Output: [1,3,2]

---

🤔 order 방식 중 postorder는?
LEFT → RIGHT → NODE

위의 그림의 노드를 postorder 순서로 진행하면? [1, 2, 3, 4, 5]가 됩니다.
(✨ All DFS traversals (preorder, inorder, postorder) in Python in 1 line 해당 글을 참고했습니다.)

✅ 최종 Solution

L→R→N 순서로 하는 것 보다 차라리 반대로 진행을 한 다음에…
리스트를 반대로 출력하는게 가장 간단한 방법이라는 것을 헤매이다 찾아냈습니다. 🫠

고로 N→R→L 순서로 진행을 해보면 root 부터 오른쪽 왼쪽 순서대로 반복하여 리스트를 만들면 됩니다!
코드는 아래와 같습니다.

def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
  def dfs(node):
    if not node: return
    ans.append(node.val)
    dfs(node.right)
    dfs(node.left)
  ans = []
  dfs(root)
  return ans[::-1]