Leetcode 145. Binary Tree Postorder Traversal (Python)

Related Topic

Depth-First-Search. Tree. Postorder-Traversal.

Description

Given a binary tree, return the Postorder traversal of its nodes’ values.

Sample I/O

Example 1

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

Output: [3,2,1]

Follow up

Recursive solution is trivial, could you do it iteratively?

Methodology

This question can be solved by Depth First Search.

This is very direction answer, you can apply dfs directly. However, for the follow up question, to solve it iteratively, you can use stack.

Code 1 (DFS)

def postorderTraversal(self, root: TreeNode) -> List[int]:
        def dfs(root,res):
            if root is None: return []
            dfs(root.left, res)
            dfs(root.right, res)
            res.append(root.val)
            return res
        return dfs(root, [])

BigO

We traversal all nodes of the tree once so O(n)

Code 2 (Iteratively)

def PostorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        stack = [root]
        while stack:
            node = stack.pop()
            if node:
                res.append(node.val)
                stack.append(node.left)
                stack.append(node.right)
        return res[::-1]

BigO

We traversal all nodes of the tree once so total time complexity is O(n)