Leetcode 144. Binary Tree Preorder Traversal (Python)

Related Topic

Depth-First-Search. Tree. Preorder-Traversal.

Description

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

Sample I/O

Example 1

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

Output: [1,2,3]

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 preorderTraversal(self, root: TreeNode) -> List[int]:
        def dfs(root, res):
            if not root: return
            res.append(root.val)
            dfs(root.left, res)
            dfs(root.right, res)
            return res
        if not root: return []
        return dfs(root,[])

BigO

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

Code 2 (Iteratively)

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

BigO

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