Binary Tree Inorder Traversal

You get the root of a binary tree. Return a list of its values in inorder.

In inorder, each node comes after its left subtree and before its right subtree.

In the examples, each tree is written row by row from the top. Each row goes left to right. None marks a missing child.

Example 1:

Input: [2,5,1,None,3,4]
       2
      / \
     /   \
    5     1
     \   /
      3 4

Output: [5, 3, 2, 4, 1]
Explanation: First comes the left side of 2: 5, then 3.
Then comes 2 itself.
Last comes the right side of 2: 4, then 1.

Example 2:

Input: [6,None,4,8]
   6
    \
     4
    /
   8

Output: [6, 8, 4]
Explanation: 6 has nothing on its left, so it comes first.
8 is the left child of 4, so 8 comes before 4.

Constraints:

• The tree has 1 to 1,000 nodes.
• Each value is a whole number from 1 to 1,000.
• All values are different.

Follow-up: Once recursion works, write it again with a loop and your own stack.