874. Iterative Inorder Traversal Using Stack

Given the root of a binary tree, return its inorder traversal computed iteratively with an explicit stack (no recursion). Return the values as an array. The tree is given as a level-order array with null for missing children.

Input: A level-order array of the tree.

Output: Array — node values in inorder.

Examples

Input: [1,null,2,3]
Output: [1,3,2]
Explanation: Iterative inorder order.

Input: [1,2,3,4,5,null,7]
Output: [4,2,5,1,3,7]
Explanation: Left, root, right.

Input: []
Output: []
Explanation: Empty tree.

Constraints

• 0<=nodes<=10^4
• -1000<=value<=1000

Asked by