LeetCode: binary-tree-postorder-traversal

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

 

Example 1:

Input: root = [1,null,2,3]

Output: [3,2,1]

Explanation:

Example 2:

Input: root = [1,2,3,4,5,null,8,null,null,6,7,9]

Output: [4,6,7,5,2,9,8,3,1]

Explanation:

Example 3:

Input: root = []

Output: []

Example 4:

Input: root = [1]

Output: [1]

 

Constraints:

• The number of the nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

 

이 문제는 preorder의 반대의 방식으로 풀면 되는 문제이다. 

 

방문한 leaf node부터 차례대로 출력해줘야 하기 때문에 이전과는 반대로 self.res를 append하는 코드를 마지막에 넣으면 된다.

 

self.postorderTraversal(root.left)

self.postorderTraversal(root.right)

self.res.append(root.val)

 

함수의 처음에 root가 없을 수 있기 때문에 if root == None: return [] 를 써주면 문제를 풀 수 있게 된다.

 

---

구현코드

 

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def __init__(self):
        self.res = []
    def postorderTraversal(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: List[int]
        """
        if root == None:
            return []
        
        self.postorderTraversal(root.left)
        self.postorderTraversal(root.right)
        self.res.append(root.val)

        return self.res