LeetCode 144. Binary Tree Preorder Traversal

'''
Given a binary tree, return the preorder traversal of its nodes' values.
'''
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution_1:

    #recursive

    def travel(self, root):

        if root:

            self.result.append(root.val)

            self.travel(root.left) 

            self.travel(root.right)        

    

    def preorderTraversal(self, root: 'TreeNode') -> 'List[int]':

        self.result = []        

        if not root:

            return self.result

        else:

            self.travel(root)

            return self.result

'''

some thoughts:

preorder = root, left, right

the iterative method:

the key is that the length of the list changes at every iteration

for loop may not work this case, change to while loop and calculate the length of the list every time

every insert left and right to root, if any
first create list of all node, then val

'''

class Solution_2:

    #iterative

    def preorderTraversal(self, root: 'TreeNode') -> 'List[int]':

        if not root:

            return []

        else:

            l = [root]

            i = 0

            while i < len(l):

                n = len(l)

                if l[i].right:                    

                    l.insert(i+1, l[i].right)

                if l[i].left:

                    l.insert(i+1, l[i].left)

                i += 1

            

            result = [j.val for j in l]

            return result