144-Binary Tree Preorder Traversal

Problem

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

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?

Thought Process

  • Solve it recursively
  • node first
  • left tree
  • right tree

White Board

Below is the white board:

Code

class TN:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Sol:
    def pre(self, root):
        res = []
        if root:
            res.append(root.val)
            self.pre(root.left)
            self.pre(root.right)

        return res

True

Complexity

  • Time complexity is O(n*m)
  • used additional ds to creat stack

Optimization

Will try to figure out a recursive solution in the future.