94. Binary Tree Inorder Traversal

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

Note: The non-recursive one is tricky. Go down left pushing to stack.

Pop stack, consume it. Point to its right.

def inorderTraversal(root):        

    res = []

    def recurse(cur):

        if cur:                

            recurse(cur.left)

            res.append(cur.val)

            recurse(cur.right)

           

    recurse(root)

    return res    

   

def inorderTraversal(root):

   

    res = []

    stack = []

    cur = root

    while cur or stack:

        while cur:

            stack.append(cur)

            cur = cur.left

        n = stack.pop()

        res.append(n.val)            

        cur = n.right

    return res