leetcode : Binary Tree Postorder Traversal

https://leetcode.com/problems/binary-tree-postorder-traversal/

Binary Tree Postorder Traversal - LeetCode

이게 easy라고..?

저번 inorder traversal에 이어서 전혀 easy하지 않은데..ㅠㅠㅠㅠ (https://leetcode.com/problems/binary-tree-inorder-traversal/)

 

class Solution:
    # @param {TreeNode} root
    # @return {integer[]}
    def postorderTraversal(self, root):
        traversal, stack = [], [(root, False)]
        while stack:
            node, visited = stack.pop()
            if node:
                if visited:
                    # add to result if visited
                    traversal.append(node.val)
                else:
                    # post-order
                    stack.append((node, True))
                    stack.append((node.right, False))
                    stack.append((node.left, False))

        return traversal

이건 솔루션에 있던거긴 한데 나도 생각한 방법, 가장 직관적이고 쉬운 방법

 

class Solution:
    # @param {TreeNode} root
    # @return {integer[]}
    def postorderTraversal(self, root):
        traversal, stack = [], [root]
        while stack:
            node = stack.pop()
            if node:
                # pre-order, right first
                traversal.append(node.val)
                stack.append(node.left)
                stack.append(node.right)

        # reverse result
        return traversal[::-1]

이건 어떻게 이런 창의성을 발휘하나 싶었던 방법

inorder : left -> me -> right

preorder : me -> left -> right

postorder : left -> right -> me

 

지금 하려는건 postorder, 그러니까 left -> right -> me인데

이걸 뒤집으면 me -> right -> left, 그니까 right subtree first preorder traversal이 된다.

만들어서 리스트를 뒤집어주면 된다.. 와 ㅋㅋㅋㅋ