Given the root of a binary tree, return the list of node values in inorder: for each node, everything in its left subtree, then the node, then everything in its right subtree. Do it without recursion: the tree may be a chain 1000 nodes deep.
Examples
1
/ \
2 3
/ \ \
4 5 6
Input: root = build_tree([1, 2, 3, 4, 5, None, 6])
Output: [4, 2, 5, 1, 3, 6]
Input: root = build_tree([1, None, 2, 3])
Output: [1, 3, 2]
Constraints
0 <= number of nodes <= 2000-10**4 <= node.val <= 10**4- Target complexity: O(n) time, O(h) extra space where h is the height.
Goals
- Produce the inorder sequence (left subtree, node, right subtree)
- Simulate the recursion with an explicit stack and a 'current' pointer
- Handle deep right- and left-skewed chains