[leetcode] 145. Binary Tree Postorder Traversal

원문)

Given a binary tree, return the postorder traversal of its nodes's values.

번역)

이진트리를 주어졌을때 그 노드값을 postorder 순회를 반환하라.


예제)

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [3,2,1]

문제접근)

왼쪽 자식 -> 오른쪽 자식 -> 부모

top-down은 할만함
하지만 bottom-up은 어려움 (stack이용)


코드)

1.  top-down

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: # top-down def postorderTraversal(self, root: TreeNode) -> List[int]: answer = [] self.top_down(root, answer) return answer def top_down(self, root: TreeNode, answer: List[int]): if root is None: return self.top_down(root.left, answer) self.top_down(root.right, answer) answer.append(root.val)

2.  bottom-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: # bottom-up def postorderTraversal(self, root: TreeNode) -> List[int]: stack = [root] output = [] while stack: node = stack.pop() if node: output.append(node.val) stack.append(node.left) stack.append(node.right) return output[::-1]